赚米
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

你希望在接下来的 n 天内，通过交易某种物品赚取至少 m 元的利润。已知该物品每天的价格走势为 p_1, p_2, \dots, p_n。交易规则如下：

- 你可以在某一天买入该物品，但必须在次日全部卖出，不能持有超过一天。
- 你只能买入整数单位的物品。
- 在价格不利时，你可以选择不进行交易。

初始时你拥有本金 X 元，通过每天选择最优交易策略，最终在第 n 天结束时，你需要把所有物品卖出，你的资金变为 F 元。你的目标是使得利润至少达到 m 元，即 F-X\ge m 。

请你计算，为了实现这一目标，所需的最小初始本金 X 应该是多少。
如果本金在 10^{18} 的范围内实现不了赚到 m 元的利润，则输出 -1。

输入描述:

- 第一行包含两个整数 n 和 m，分别表示天数和所需的利润。满足 1\le n \le 10^6, 1 \le m \le 10^9 
- 第二行包含 n 个整数 p_1, p_2, \dots, p_n，表示物品每天的价格，满足1 \le p_i \le 10^9.

输出描述:

输出一个整数，表示达到至少 m 元利润所需的最小初始本金 X。
示例1

输入

复制 
5 10
3 5 4 8 6

输出

复制 
6

说明


示例2

输入

复制 
4 4
1 1 1 1

输出

复制 
-1

说明

赚不到钱

备注: