[AdditionalFile5091.zip](file://AdditionalFile5091.zip?type=additional_file)

#5091. 「POI2019 R3」鸟类学家 Ornithologist

标签: 传统 | 时间限制: 10000 ms | 内存限制: 8 MiB |

题目描述

题目译自 XXVI Olimpiada Informatyczna – III etap Ornitolog

请注意本题较小的内存限制。

鸟类学家 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, 2, 3$ 唱完，雄鸟 $3$ 飞离，下一首为「我的小鸽子」。第二首由鸟 $4, 5, 6$ 唱完，雌鸟 $6$ 飞离，下一首为「我爱你小鸽子」。第三首由鸟 $7, 8, 9, 10, 1$ 唱完，雄鸟 $1$ 飞离，下一首为「我的小鸽子」。第四首由鸟 $2, 4, 5$ 唱完，雌鸟 $5$ 飞离。第五首由鸟 $7, 8, 9$ 唱完，雌鸟 $9$ 飞离。第六首由鸟 $10, 2, 4$ 唱完，雌鸟 $8$ 飞离，故答案为 $8$。已飞离的鸟不再参与演唱。

附加样例

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

数据范围与提示

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

详细子任务附加限制及分值如下表所示。