鸟类学家 Ornithologist

题目描述

鸟类学家 Bajtazar 发现了已灭绝的拜托城数字鸽（Ectopistes digitorius）的历史记录。据记载，这种鸟类有独特的求偶习俗。

求偶仪式涉及 $n$ 只雄鸟和 $m$ 只雌鸟：

• 雄鸟编号为 $1$ 至 $n$
• 雌鸟编号为 $n+1$ 至 $n+m$

它们围成一圈，按编号 $1$ 至 $n+m$ 顺序站立，轮流唱求偶曲。

鸟类有两首求偶曲：

• 「我的小鸽子」含 $a$ 个音符
• 「我爱你小鸽子」含 $b$ 个音符

鸟儿按圈内顺序逐一唱一个音符：

• 从编号 $1$ 的鸟开始，唱「我的小鸽子」的第一个音符
• 唱完一首曲的最后音符的鸟儿飞离
• 剩余鸟儿从下一只鸟继续唱
• 若飞离的是雄鸟，下一首曲为「我的小鸽子」
• 若为雌鸟，则唱「我爱你小鸽子」

Bajtazar 想知道第 $k$ 只飞离的鸟儿的编号。

输入格式

第一行包含五个正整数 $n$, $m$, $a$, $b$, $k$ ($k, a, b \leq n+m$)，分别表示雄鸟数、雌鸟数、「我的小鸽子」音符数、「我爱你小鸽子」音符数，以及 Bajtazar 关注的第 $k$ 只飞离的鸟。

输出格式

第一行输出一个整数，表示第 $k$ 只飞离的鸟儿的编号。

样例

输入

4 6 3 5 6

输出

8

解释

有 $4$ 只雄鸟（编号 $1, \ldots, 4$）和 $6$ 只雌鸟（编号 $5, \ldots, 10$）。「我的小鸽子」有 $3$ 个音符，「我爱你小鸽子」有 $5$ 个音符。需找出第 $6$ 只飞离的鸟。

过程如下：

1. 第一首曲由鸟 $1, 2, 3$ 唱完，雄鸟 $3$ 飞离，下一首为「我的小鸽子」
2. 第二首由鸟 $4, 5, 6$ 唱完，雌鸟 $6$ 飞离，下一首为「我爱你小鸽子」
3. 第三首由鸟 $7, 8, 9, 10, 1$ 唱完，雄鸟 $1$ 飞离，下一首为「我的小鸽子」
4. 第四首由鸟 $2, 4, 5$ 唱完，雌鸟 $5$ 飞离
5. 第五首由鸟 $7, 8, 9$ 唱完，雌鸟 $9$ 飞离
6. 第六首由鸟 $10, 2, 4$ 唱完，雌鸟 $8$ 飞离，故答案为 $8$

附加样例

• $n=10$, $m=10$, $a=2$, $b=5$, $k=1$，答案 $2$
• $n=500$, $m=400$, $a=3$, $b=3$, $k=500$，答案 $899$
• $n=100000$, $m=150000$, $a=2$, $b=2$, $k=150001$，答案 $100003$
• $n=5000000$, $m=5000000$, $a=1$, $b=1$, $k=10000000$，答案 $10000000$

数据范围与提示

所有测试点满足 $1 \leq n, m \leq 10^9$, $1 \leq a, b \leq 10000$。

子任务分配：

子任务	附加限制	分值
1	$n+m \leq 1000$	12
2	$n+m \leq 250000$	20
3	$n+m \leq 5000000$, $k \leq 1000000$	18
4	$k \leq 3000000$	22
5	无附加限制	28