← 返回题目列表

Codeforces · 1068/A

A. 生日

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

Ivan 正在收集硬币。只有 $$$N$$$ 种不同的收藏硬币,Ivan 有 $$$K$$$ 个。他很快就要庆祝生日了,所以他所有的 $$$M$$$ 朋友决定送他硬币。他们都同意三个条款:

- 每个人都必须赠送与其他人一样多的硬币。
- 给予 Ivan 的所有硬币必须不同。
- 礼物中总共不少于 $$$L$$$ 硬币,必须是 Ivan 收藏中的新硬币。

但他的朋友们不知道 Ivan 已经收藏了哪些硬币。他们不想花钱,所以他们想购买满足所有条件的最低数量的硬币,无论伊万的收藏如何。帮助他们找到最小数量的硬币或定义不可能满足所有条件。

输入

输入的唯一行包含 4 个整数 $$$N$$$, $$$M$$$, $$$K$$$, $$$L$$$ ($$$1 \le K \le N \le 10^{18}$$$; $$$1 \le M, \,\, L \le 10^{18}$$$) — 不同硬币的数量,Ivan 的数量朋友们,伊万收藏的规模和钱币数量,在伊万的收藏中一定是新的。

输出

打印一个数字 - 一位朋友可以赠送满足所有条件的最少硬币数量。如果不可能满足所有三个条件,则打印“-1”(不带引号)。

示例

输入 #1

20 15 2 3

输出 #1

1

输入 #2

10 11 2 4

输出 #2

-1

注意

在第一个测试中,每个朋友提供一枚硬币就足够了,因为他将获得 15 种不同的硬币,其中 13 枚肯定是新的。

在第二次测试中,Ivan 有 11 个朋友,但只有 10 个不同的硬币。所以所有的朋友都不能送他不同的硬币。