题目描述

小蓝是某大型物流中心的仓储管理员。今天，系统下达了一项紧急任务：需要将 $N$ 个标准集装箱全部入库，并分配到 $M$ 个货架上。

货架从左到右编号为 $1, 2, \dots, M$。由于自动化机械臂将集装箱运送到不同货架的距离不同，将 $1$ 个集装箱放入第 $i$ 个货架需要消耗 $i$ 单位电力。

公司要求本次入库任务的总耗电量必须在闭区间 $[L, R]$ 内。同时，为了避免单个货架承重过高，小蓝希望让放置集装箱数量最多的货架尽可能少放一些集装箱。

形式化地说，你需要构造一个非负整数序列 $a_1, a_2, \dots, a_M$，其中 $a_i$ 表示第 $i$ 个货架放置的集装箱数量。该序列需要满足：

• 所有集装箱都被分配到货架上，即 $\sum_{i=1}^{M} a_i = N$；
• 总耗电量满足 $L \le \sum_{i=1}^{M} i \times a_i \le R$。

在所有满足条件的分配方案中，请求出 $\max(a_1, a_2, \dots, a_M)$ 的最小可能值。如果不存在满足条件的分配方案，输出 $-1$。

输入格式

输入共一行，包含四个整数 $N, M, L, R$，分别表示集装箱数量、货架数量、总耗电量下界和总耗电量的上界。

输出格式

输出一行，包含一个整数，表示 $\max(a_i)$ 的最小可能值。

如果不存在满足条件的分配方案，输出 $-1$。

5 3 13 14

3

提示

【样例说明】

下面两种方案都满足总耗电量限制：

• $a_1 = 0, a_2 = 2, a_3 = 3$，总耗电量为 $0 \times 1 + 2 \times 2 + 3 \times 3 = 13$，此时 $\max(a_i) = 3$；
• $a_1 = 0, a_2 = 1, a_3 = 4$，总耗电量为 $0 \times 1 + 1 \times 2 + 4 \times 3 = 14$，此时 $\max(a_i) = 4$。

第一种方案的最大货架放置数量更小。可以证明不存在使 $\max(a_i)$ 小于 $3$ 的合法方案，因此答案为 $3$。

【评测用例规模与约定】

对于 $40\%$ 的数据，保证 $N, M \le 40$。

对于所有数据，保证 $1 \le N, M \le 20000$，$1 \le L \le R \le NM$。