著名的 Codeforces 幼儿园由 n 个孩子组成,编号为 1 到 n。他们每个人的父母都会给他们卢布零用钱。
今天,他们要去镇上最著名的糖果店。这家商店出售包装糖果:对于 1 到 m 之间的所有 i(含),它出售的包装恰好包含 i 颗糖果。一颗糖果售价 1 卢布,因此包含 x 颗糖果的包裹售价 x 卢布。
从孩子1开始,孩子们会轮流购买糖果。在一个回合中,孩子i会购买一个糖果包。由于Codeforces幼儿园的竞争性很强,在一个回合中,孩子购买的包裹中所含的糖果数量总是严格大于孩子在上一个回合中购买的包裹中所含的糖果数量(第一轮例外:第一个孩子可以购买任何包裹)。然后,轮到孩子 i + 1,或者如果轮到孩子 n,则轮到孩子 1。这个过程可以随时结束,但在购买过程结束时,所有孩子必须拥有相同数量的糖果包。当然,每个孩子花在糖果上的金额不能超过他们的津贴。
您在糖果店工作,想为孩子们准备糖果。打印出糖果店可以卖给孩子们的最大糖果数量。如果孩子们无法购买任何糖果(由于零用钱不足),请打印 0。
输入
第一行包含两个空格分隔的整数n和m(2 ≤ n ≤ 2·105, 2 ≤ m ≤ 5·106, n ≤ m),分别表示孩子的数量和糖果店出售的一包糖果的最大数量。
接下来是 n 行,每行包含一个不超过 $$\frac{m(m+1)}{2}$$ 的正整数,表示孩子的零用钱,以卢布为单位。津贴按照从孩子 1 到孩子 n 的顺序发放。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。建议使用 cin、cout 流(也可以使用 %I64d 指定符)。
输出
打印一个整数,表示糖果店可以出售的最大糖果数量。
示例
输入 #1
2 5 5 10
输出 #1
13
输入 #2
3 8 8 16 13
输出 #2
32
输入 #3
2 5000000 12500002500000 12500002500000
输出 #3
12500002500000
注意
对于第一个示例,将导致购买 13 颗糖果的场景之一如下。
- 第 1 回合。孩子 1 购买 1 颗糖果。
- 第 2 回合。孩子 2 购买了 3 颗糖果。
- 第 3 回合。孩子 1 购买了 4 颗糖果。
- 第 4 回合。孩子 2 购买了 5 颗糖果。