Рабочее место участника

На планете Плюк открылся новый космический кегельбан. Поле для кегельбана представляет собой бесконечную плоскость, на которой расставлены кегли.

Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом `r` метров. Все кегли одинаковые. Кегли расставлены по следующим правилам. Кегли образуют `n` рядов, в первом ряду стоит одна кегля, во втором – две, и так далее. В последнем `n`-м ряду стоит `n` кеглей. Введем на плоскости систему координат таким образом, чтобы единица измерения была равна одному километру. Центр единственной кегли в первом ряду находится в точке `(0, 0)`. Центры кеглей во втором ряду находятся в точках `(–1, 1)` и `(1, 1)`. Таким образом, центры кеглей в `i`-м ряду находятся в точках с координатами `(–(i – 1), i – 1)`, `(–(i – 3), i – 1)`, …, `(i – 1, i – 1)`.

Игра происходит следующим образом. Используется шар с радиусом `q` метров. Игрок выбирает начальное положение центра шара `(x_c, y_c)` и вектор направления движения шара `(v_x, v_y)`. После этого шар помещается в начальную точку и двигается, не останавливаясь, в направлении вектора `(v_x, v_y)`. Считается, что шар сбил кеглю, если в процессе движения шара имеет место ситуация, когда у шара и кегли есть общая точка. Сбитые кегли не меняют направления движения шара и не сбивают соседние кегли при падении.

На рисунке приведен пример расположения кеглей для `r = 500`, `n = 4` и шара для `q = 1000`, `x_c = –2`, `y_c = –2`, `v_x = 1`, `v_y = 1`.

Требуется написать программу, которая по заданным радиусу кегли `r`, количеству рядов кеглей `n`, радиусу шара `q`, его начальному положению `(x_c, y_c)` и вектору направления движения `(v_x, v_y)` определяет количество кеглей, сбитых шаром.

Первая строка входного файла содержит два целых числа: `r` и `n`, разделенных ровно одним пробелом (`1 ≤ r ≤ 700`, `1 ≤ n ≤ 200 000`).

Вторая строка входного файла содержит целое число `q` (`1 ≤ q ≤ 10^9`).

Третья строка входного файла содержит два целых числа `x_c` и `y_c`, разделенных ровно одним пробелом (`–10^6\ ≤ "xc" ≤ 10^6`, `–10^6\ ≤ "yc"`, `1000*y_c\ <\ –(r + q)` ).

Четвертая строка входного файла содержит два целых числа `v_x` и `v_y`, разделенных ровно одним пробелом (`–10^6\ ≤ v_x ≤ 10^6`, `0 < v_y ≤ 10^6`).

Выходной файл должен содержать одно целое число – количество сбитых кеглей.

500 4
1000
-2 -2
1 1

7

Пояснения к примеру

Рисунок ниже показывает, какие кегли будут сбиты (такие кегли обозначены «х»).

Правильные решения для тестов, в которых `1 ≤ n ≤ 1000` и `"vx" = 0`, будут оцениваться из 20 баллов.

Правильные решения для тестов, в которых `1 ≤ n ≤ 1000` и `v_x ≠ 0`, будут оцениваться еще из 20 баллов.

Правильные решения для тестов, в которых `1000 < n ≤ 200 000` и `v_x = 0`, будут оцениваться еще из 20 баллов.

Чтобы получить оставшиеся 40 баллов, решение должно правильно работать также для тестов, в которых `1000 < n ≤ 200 000` и `v_x ≠ 0`.