#P1961. [Baltic2010]candies

    ID: 983 传统题 3000ms 64MiB 尝试: 184 已通过: 63 难度: 8 上传者: 标签>CF2400提高+/省选-0/1 背包计数 DP倒序更新避免重复使用暴力枚举位集加速背包Day2

[Baltic2010]candies

[BalticOI 2010 Day2] Candies

题目描述

给定一个长度为 NN 的序列 B1,B2,…,BNB_1,B_2,\dots,B_N。

一个整数 MM 能够被表示出来当且仅当从序列中任取 KK 个数 A1,A2,…,AKA_1,A_2,\dots,A_K,使得 ∑i=1kAi=M\sum_{i=1}^{k}A_i=M。

你需要修改序列中的一个数 PP,使得尽可能多的整数能够被表示出来。

输入格式

输入第一行一个整数 NN。

第二行 NN 个整数 B1,B2,…,BNB_1,B_2,\dots,B_N。

输出格式

输出一行两个整数 P,QP,Q,以一个空格隔开。

表示序列中的一个数字 PP 修改成 QQ。

如果有多种方案,则输出的 PP 尽可能小。 PP 最小时如有多种方案,则输出的 QQ 尽可能小。

样例 #1

样例输入 #1

4
1 3 4 4

样例输出 #1

4 9

样例 #2

样例输入 #2

5
3 3 3 3 3

样例输出 #2

3 1

提示

对于 100%100\% 的数据,保证 2≤N≤1002\le N\le 100,1≤Bi≤70001\le B_i\le 7000。

题目译自 BalticOI 2010 Day2 T2 Candies。