← 返回题目列表

Codeforces · 1063/D

D. 儿童糖果

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

儿童节,孩子们围成一圈跳舞。当音乐停止时,孩子们仍然站成一圈。然后莉娜想起来,她的父母给了她一个糖果盒,里面装着 $$$k$$$ 糖果“Wilky May”。莉娜并不是一个贪心的人,所以她决定把自己所有的糖果都送给圈里的朋友们。莉娜知道,她的一些朋友喜欢吃甜食,而另一些则不喜欢。如果盒子里至少有两颗糖果,爱吃甜食的人从盒子里取出两颗糖果,否则取出一颗。莉娜的其他朋友总是从盒子里拿走一颗糖果。

在开始给糖果之前,莉娜走出了圈子,之后正好剩下$$$n$$$人。 Lena 按顺时针顺序用从 $$$1$$$ 开始的正整数对她的朋友进行编号,索引 $$$1$$$ 被分配给她最好的朋友 Roma。

最初,Lena 将盒子交给编号为 $$$l$$$ 的朋友,之后每个朋友(从朋友编号 $$$l$$$ 开始)从盒子里取出糖果,并按顺时针顺序将盒子传递给下一个朋友。该过程以好友 $$$r$$$ 拿走最后一颗糖果(或两颗,谁知道)和空盒子结束。请注意,莉娜的一些朋友可能多次从盒子里拿走糖果,也就是说,盒子可能已经转了好几圈才变空。

Lena 不知道她的哪些朋友爱吃甜食,但她感兴趣的是最多可能有多少个朋友爱吃甜食。如果这种情况不可能发生,并且莉娜的观察被证明是错误的,请告诉她这件事。

输入

唯一的一行包含四个整数 $$$n$$$、$$$l$$$、$$$r$$$ 和 $$$k$$$ ($$$1 \le n, k \le 10^{11}$$$, $$$1 \le l, r \le n$$$) — 圈子里的孩子数量、收到糖果盒的朋友数量、朋友,分别拿走了盒子里最后一颗糖果和最初数量的糖果。

输出

精确地输出一个整数——Lena 的朋友中爱吃甜食的最大可能数量,如果 Lena 错了,则输出“-1”(为了清楚起见,用引号引起来)。

示例

输入 #1

4 1 4 12

输出 #1

2

输入 #2

5 3 4 10

输出 #2

3

输入 #3

10 5 5 1

输出 #3

10

输入#4

5 4 5 6

输出#4

-1

注意

在第一个例子中,任意两个朋友都可以是甜食爱好者,这样每个人都会收到两次糖果盒,最后一个拿到糖果的人将是第四个朋友。

在第二个示例中,爱吃甜食的人可以是任意三个朋友,但第三个位置上的朋友除外。

在第三个例子中,只有一个朋友会拿糖果,但他仍然是一个爱吃甜食的人,但只是不能拿两块糖果。圈子里的其他朋友也都是爱吃甜食的人,只是一次都吃不到糖。

在第四个例子中,Lena 错了,这种情况不可能发生。