← 返回题目列表

Codeforces · 767/B

B. 队列

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

终于!瓦夏已经成年了,这意味着他终于可以拿到护照了!为此,他需要去护照办公室,但事情没那么简单。护照办公室只有一名接待员,人们在办公室真正开放之前就可以排起长队。瓦夏想明天去护照办公室。

他知道接待员在午夜过后 ts 分钟后开始工作,并在午夜后 tf 分钟后关闭(因此 (tf - 1) 是接待员仍在工作的最后一分钟)。接待员在队列中的每个人身上花费了 t 分钟的时间。如果接待员在 t 分钟内停止工作,他就会停止为访客提供服务(除了他已经服务过的访客)。

Vasya 还知道明天正好有 n 位访客来。对于每位访客来说,瓦夏都知道他何时来到护照办公室。每个游客都排队等候,直到得到服务后才离开。如果有访客到来时接待员有空(特别是如果前一位访客刚刚得到服务且队列为空),则接待员立即开始为新来者提供服务。

“接待1”

对于每个访客来说,他来到护照办公室的时间点都是肯定的。如果 Vasya 需要的话,他可以在零点(即午夜)到办公室,但他只能在整数时间点到办公室。如果瓦夏与其他几位访客同时到达护照办公室,他就会向他们让行,并站在最后一个访客后面。

Vasya 希望在接待员为他服务的时间点到达,并且他会在队列中花费尽可能少的时间。帮助他!

输入

第一行包含三个整数:接待员开始工作的时间点ts、接待员停止工作的时间点tf以及接待员在每个访客上花费的时间t。第二行包含一个整数 n — 访客数量 (0 ≤ n ≤ 100 000)。第三行包含非降序的正整数——访客到达护照办公室的时间点。

所有时间均以分钟为单位设置,不超过1012;保证 ts < tf.还保证 Vasya 可以在接待员为他服务的时间点到达护照办公室。

输出

打印单个非负整数 - Vasya 应到达护照办公室的时间点。如果瓦夏与其他几位访客同时到达护照办公室,他就会让路,让最后一个访客排队。如果有很多答案,您可以打印其中任何一个。

示例

输入 #1

10 15 2
2
10 13

输出 #1

12

输入 #2

8 17 3
4
3 4 5 8

输出 #2

2

注意

在第一个示例中,第一位访客恰好在接待员开始工作的时间点到来,并为他提供了两分钟的服务。午夜过后 12 分钟,接待员停止为第一位访客提供服务,如果此时 Vasya 到达,他将立即得到服务,因为下一位访客只会在午夜过后 13 分钟到来。

在第二个示例中,Vasya 必须先于其他人来接受服务。