Вы одиночный робот, находящийся изначально в точке \(0\) на окружности
с периметром \(L\) (\(1 \le L \le 10^9\)). Вы можете двигаться на \(1\) за секунду
по или против часовой стрелки. Все движения в этой задаче непрерывны.
Ваша цель - разместить ровно \(R-1\) роботов так, чтобы в конце каждые
два последовательных робота были на расстоянии \(L/R\) друг от друга
(\(2\le R\le 20\), \(L\) делится нацело \(R\)). Всего имеется \(N\)
(\(1\le N\le 10^5\)) точек активации, \(i\)-ая из которых расположена
на расстоянии \(a_i\) против часовой стрелки от \(0\) (\(0\le a_i<L\)).
Если в текущий момент Вы находитесь в точке активации, Вы можете поместить
робота в эту точку. Все роботы (включая оригинального) двигаются
против часовой стрелки со скоростью \(1\) единица за \(K\) секунд
(\(1\leq K\leq 10^6\)).
Вычислите минимальное время, которое необходимо,
чтобы достичь цель.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(L\),
\(R\),
\(N\), and
\(K\).
Следующая строка содержит \(N\) разделённых одиночными пробелами
целых чисел \(a_1,a_2,\dots,a_N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Минимальное время, требуемое чтобы достичь цели.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 2 1 2
6
|
22
|