Заочные олимпиады: Заключительный этап - первый тур

Компания «Nanosoft» готовится удивить мир принципиально новой игрой для смартфонов «Две башни». Ее ключевая особенность заключается в том, что играть в нее смогут даже самые маленькие дети. Во-первых, для управления используется всего одна кнопка. Во-вторых, проиграть просто невозможно (правда, игроку может надоесть часами нажимать на одну и ту же кнопку).

Игровое поле представляет собой бесконечную горизонтальную ленту, разбитую на ячейки, пронумерованные целыми числами слева направо (см. рис.). Изначально в ячейках с отрицательными номерами расположена армия монстров, у каждого из которых есть некоторое количество единиц здоровья. А именно, в ячейках \(-1, -2, \ldots, -K\) расположены монстры с 1 единицей здоровья, в следующих \(K\) ячейках (с номерами \(-(K+1), \ldots, -2K\)) расположены монстры с 2 единицами здоровья и так далее. Таким образом, для каждого целого положительного числа \(i\) в ячейке с номером \(-i\) изначально находится монстр с \(\left\lceil\frac{i}{K}\right\rceil\) единицами здоровья. Кроме того, на ленте расположены две башни, каждая из которых контролирует некоторый отрезок ленты: первой башне соответствуют все ячейки с \(A\) по \(B\) включительно, а второй - ячейки с \(C\) по \(D\) включительно (\(0 \leqslant A \leqslant B \lt C \leqslant D\)).

Например, при \(K = 3\), \(A = B = 1\), \(C = 3\), \(D = 4\) исходная позиция будет выглядеть следующим образом:

После очередного нажатия на кнопку происходит следующее. Сначала вся армия сдвигается на одну позицию вправо. Затем каждая башня производит выстрел по самому правому монстру, находящемуся в области ее видимости, отнимая у него единицу здоровья. Если у монстра отнимают последнюю единицу здоровья, он немедленно умирает и исчезает.

Игра заканчивается, как только впервые в ячейке с номером \(D + 1\) окажется монстр.

Как вы уже могли заметить, главная проблема игры заключается в том, что для выигрыша может потребоваться слишком много нажатий на кнопку, поэтому для некоторых особо сложных уровней решено ограничить возраст игроков, допускаемых к его прохождению. В связи с этим вам нужно определить, сколько нажатий на кнопку потребуется для победы на данном уровне, который описывается числами \(K\),\(A\), \(B\), \(C\) и \(D\).