← 返回题目列表

AtCoder · abc365_c

E. 交通费用

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

分数: 300 点

问题陈述

有 N 参加活动的人数,以及活动的交通费用 i- 第一个人是 A_i 日元。

活动组织者高桥决定设定最高限额 x 交通补贴。人均补贴 i 将是 \min(x, A_i) 日元。在这里, x 必须是非负整数。

鉴于高桥的预算是 M 日元,他想要所有人的交通补贴总额 N 人最多 M 日元,补贴限额的最大可能值是多少 x?

如果补贴限额可以无限大,请报告。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^{14}
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

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

N M
A_1 A_2 \ldots A_{N}

输出

打印补贴限额的最大值 x 满足预算条件,为整数。

如果补贴限额可以无限大,则打印 infinite 。


示例输入 1

4 8
1 3 2 4

示例输出 1

2

如果补贴限额设置为 2 日元,全体交通补贴总额 N 人是 \min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7 日元,在预算之内 8 日元。

如果补贴限额设置为 3 日元,全体交通补贴总额 N 人是 \min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9 日元,超出预算 8 日元。

因此,补贴限额的最大可能值为 2 日元。


示例输入 2

3 20
5 3 2

示例输出 2

infinite

补贴限额可以无限大。


示例输入 3

10 23
2 5 6 5 2 1 7 9 7 2

示例输出 3

2