С новым телом наш идол Арома Белая (или лучше было сказать Каори Минамийа?) начинает восстанавливать своё потерянное прошлое через OS-пространство.
Это пространство можно представить как 2D плоскость, с бесконечным количеством устройств с данными, пронумерованных с \(0\). Координаты устройств можно описать следующим образом:
- Координаты \(0\)-го устройства равны \((x_0, y_0)\)
- Для \(i > 0\), координаты \(i\)-го устройства равны \((a_x \cdot x_{i-1} + b_x, a_y \cdot y_{i-1} + b_y)\)
Изначально Арома расположена в точке \((x_s, y_s)\). Она может находиться в OS-пространстве не более \(t\) секунд, после этого ей придётся вернуться в реальный мир. Чтобы вернутся в реальный мир не требуется возвращаться в изначальную точку \((x_s, y_s)\).
Внутри OS-пространства Арома может делать следующие действия:
- Из точки \((x, y)\) Арома может перейти в одну из следующих точек \((x-1, y)\), \((x+1, y)\), \((x, y-1)\) или \((x, y+1)\). Это действие занимает \(1\) секунду.
- Если Арома стоит в точке с устройством, то она может его собрать. Можно считать, что это действие занимает \(0\) секунд. Разумеется, каждое устройство можно собрать не более одного раза.
Арома хочет собрать как можно больше данных перед тем как вернётся назад. Помогите ей определить максимальное количество устройств с данными, которые она сможет собрать за \(t\) секунд.
Выходные данные
Выведите одно целое число — максимальное количество устройств с данными которые Арома сможет собрать за \(t\) секунд.
Примечание
Во всех трёх примерах, координаты первых \(5\) устройств равны \((1, 1)\), \((3, 3)\), \((7, 9)\), \((15, 27)\) и \((31, 81)\) (напомним, что устройства пронумерованы начиная с \(0\)).
В первом примере оптимальный маршрут чтобы собрать \(3\) вершины выглядит следующим образом:
- Перейти в точку \((3, 3)\) и собрать \(1\)-е устройство. Это занимает \(|3 - 2| + |3 - 4| = 2\) секунд.
- Перейти в точку \((1, 1)\) и собрать \(0\)-е устройство. Это занимает \(|1 - 3| + |1 - 3| = 4\) секунд.
- Перейти в точку \((7, 9)\) и собрать \(2\)-е устройство. Это занимает \(|7 - 1| + |9 - 1| = 14\) секунд.
Во втором примере оптимальный маршрут чтобы собрать \(2\) вершины выглядит следующим образом:
- Собрать \(3\)-е устройство. Это занимает ноль секунд.
- Перейти в точку \((7, 9)\) и собрать \(2\)-е устройство. Это занимает \(|15 - 7| + |27 - 9| = 26\) секунд.
В третьем примере Арома не может собрать ни одного устройства. Пожалуй стоило отдохнуть, а не рваться в OS-пространство без подготовки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 2 3 1 0
2 4 20
|
3
|
|
2
|
1 1 2 3 1 0
15 27 26
|
2
|
|
3
|
1 1 2 3 1 0
2 2 1
|
0
|