1260 - 转变数组后最接近目标值的数组和

给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近  target (最接近表示两者之差的绝对值最小)。

如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。

请注意,答案不一定是 arr 中的数字。

输入

第一行为整数n,表示数组有n个数

第二行为n个整数,表示数组元素

第三行为整数target,表示需要达到的数组和

输出

最接近 target 的整数的最小值

样例

输入

3
4 9 3
10

输出

3

输入

3
2 3 5
10

输出

5

输入

5
60864 25176 27249 21296 20204
56803

输出

11361

提示

1 <= arr.length <= 10^4

1 <= arr[i], target <= 10^5

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题