Diggy Diggy Hole
TopCoder TCO2020, North America Regional
Time Limit: 2s, Memory Limit: 128MiB
По време на Персеидите N падащи звезди паднаха в градината на Ели. Момичето не обича камъни (било то и с извънземен произход) в градината си, затова е решила да изкопае дупка и да пусне всеки един от тях в нея.
Ще считаме градината на Ели като квадрат с размер M на M крачки, разделен на клетки с размер 1 на 1 крачка. Всяка клетка може да бъде индексирана с двойката цели числа (Xi, Yi), задаващи, съответно, нейната колона и ред. Най-лявата колона е 0, а най-дясната е M-1. Най-долният ред е 0, а най-горният е M-1.
Във всяка клетка са паднали нула, един или повече метеорита. Дупката, която Ели ще изкопае, ще бъде в една от клетките. Ако в същата клетката има паднали метеорити, ще счетем, че те отиват директно в дупката без да се налага Ели да ги мести до там. Всеки друг метеорит, обаче, трябва да бъде донесен до дупката.
Момичето няма проблем да ходи колкото си иска из градината (включително през клетката, в която е изкопана дупката), като винаги от дадена клетка се премества в някоя от съседните по хоризонтала или вертикала (до четири) такива. Ходенето без метеорит не ѝ коства никакво усилие. Тъй като метеоритите са тежки, обаче, във всеки един момент тя може да носи най-много по един от тях, като преместването му от текущата му клетка в съседна такава й коства една единица усилие.
Сега Ели се чуди колко е минималното нужно сумарно усилие за преместването на всички метеорити до дупката, при оптимален избор къде да е тя?
Тъй като падналите метеорити са наистина много, ще генерираме клетките, в които са паднали, по следния начин. Първият от тях е паднал в клетката (X1, Y1). Всеки следващ е паднал в (Xi, Yi), където Xi = (Xi-1 * A + B) % M, и Yi = (Yi-1 * C + D) % M.
Ще считаме градината на Ели като квадрат с размер M на M крачки, разделен на клетки с размер 1 на 1 крачка. Всяка клетка може да бъде индексирана с двойката цели числа (Xi, Yi), задаващи, съответно, нейната колона и ред. Най-лявата колона е 0, а най-дясната е M-1. Най-долният ред е 0, а най-горният е M-1.
Във всяка клетка са паднали нула, един или повече метеорита. Дупката, която Ели ще изкопае, ще бъде в една от клетките. Ако в същата клетката има паднали метеорити, ще счетем, че те отиват директно в дупката без да се налага Ели да ги мести до там. Всеки друг метеорит, обаче, трябва да бъде донесен до дупката.
Момичето няма проблем да ходи колкото си иска из градината (включително през клетката, в която е изкопана дупката), като винаги от дадена клетка се премества в някоя от съседните по хоризонтала или вертикала (до четири) такива. Ходенето без метеорит не ѝ коства никакво усилие. Тъй като метеоритите са тежки, обаче, във всеки един момент тя може да носи най-много по един от тях, като преместването му от текущата му клетка в съседна такава й коства една единица усилие.
Сега Ели се чуди колко е минималното нужно сумарно усилие за преместването на всички метеорити до дупката, при оптимален избор къде да е тя?
Тъй като падналите метеорити са наистина много, ще генерираме клетките, в които са паднали, по следния начин. Първият от тях е паднал в клетката (X1, Y1). Всеки следващ е паднал в (Xi, Yi), където Xi = (Xi-1 * A + B) % M, и Yi = (Yi-1 * C + D) % M.
Вход
На единствен ред на стандартния вход ще бъдат зададени разделени с интервали осемте цели числа N, M, X1, Y1, A, B, C, D.
Изход
На стандартния изход изведете едно цяло число – минималното сумарно усилие, нужно на Ели да премести всички метеорити в дупката, при оптимален избор в коя клетка да е тя.
Ограничения
- 1 ≤ N, M ≤ 10,000,000
- 0 ≤ X1, Y1, A, B, C, D < M
| Примерен Вход | Примерен Изход |
|---|---|
| 6 20 16 7 11 3 6 2 | 42 |
Координатите на метеоритите са: {(16, 7), (19, 4), (12, 6), (15, 18), (8, 10), (11, 2)}.
Една от възможните позиции на дупката, при които получаваме този отговор, е (13, 7).
Една от възможните позиции на дупката, при които получаваме този отговор, е (13, 7).