Задача 7. Космический кегельбан ≡

Условие

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

Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом 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) определяет количество кеглей, сбитых шаром.

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

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

Система оценивания

Правильные решения для тестов, в которых 1 ≤ n ≤ 1000 и v_x = 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.

Формат входного файла

Первая строка входного файла содержит два целых числа: r и n, разделенных ровно одним пробелом.

Вторая строка входного файла содержит целое число q.

Третья строка входного файла содержит два целых числа x_c и y_c, разделенных ровно одним пробелом.

Четвертая строка входного файла содержит два целых числа v_x и v_y, разделенных ровно одним пробелом.

Формат выходного файла

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

Ограничения

1 ≤ r ≤ 700, 1 ≤ n ≤ 200 000

1 ≤ q ≤ 10⁹

−10⁶ ≤ x_c ≤ 10⁶, −10⁶ ≤ y_c, 1000 × y_c < −(r + q)

−10⁶ ≤ v_x ≤ 10⁶, 0 < v_y ≤ 10⁶

Примеры тестов

500 4
1000
-2 -2
1 1

7