← 返回题目列表

AtCoder · abc192_f

F. 药水

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 种材料。材质 i 拥有的魔力为 A_i.

魔术师高桥想要从这些材料中选择一种或多种并将它们混合来制作药剂。

在他混合制作药剂的那一刻 k 多种材料,药剂的魔力是所使用材料的总和。然后,每一秒,它的魔力都会增加 k。请注意,魔力的增加是一个离散的而非连续的过程。

高桥只会一次混合材料 0。他最快什么时候才能得到魔力正好的药剂? X?

在限制条件下,可以证明可以制作出魔力恰好为 X.

约束

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 10^7
  • 10^9 \leq X \leq 10^{18}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N X
A_1 \ldots A_N

输出

打印他最早能获得魔力正好为的药水的时间 X.


示例输入 1

3 9999999999
3 6 8

示例输出 1

4999999994

混合材料制成的药水 1 和材料 3 拥有的魔力为 3+8=11 时间 0,并且增加 2 每秒,所以它将是 9999999999 时间 4999999994,这是最早的可能时间。

所有材料混合而成的药水 1, 2, 3 将拥有以下魔力 9999999998 时间 3333333327 和 10000000001 时间 3333333328,所以它永远不会完全是 9999999999.


示例输入 2

1 1000000000000000000
1

示例输出 2

999999999999999999