Pairing - Hard
TopCoder SRM 606
Time Limit: 0.4s, Memory Limit: 4MiB
Ели е много ентусиазирана! Тя ще участва в страхотна инициатива: университети от целия свят ще сътрудничат в голям проект. Тъй като в проекта има много неща за вършене се взе решение участниците ще бъдат разделени по двойки. Сега на организаторите на инициативата остава да разделят участниците по двойки.

Всеки двама човека могат да участват в двойка, независимо дали са от един и същ университет или не. Все пак е странно, когато се случи и двамата човека да се казват по един и същ начин. Затова, организаторите искат да формират възможно най-много двойки, в които хората са с различни имена.

По дадена информация за имената на участниците от всеки университет, можете ли да определите максималния брой двойки с хора с различни имена?
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и M – съответно броя университети и броя различни имена. За простота, ще представяме имената като цели числа между 0 и M-1, включително. Очевидно, различни имена са представени с различни числа. На всеки от следващите N реда ще има по една четворка от цели числа Ci Fi Ai Bi. Ci показва колко участника от съответния университет ще се включат в проекта. Името на първия човек от този университет е P1 = Fi. Имената на останалите участници от този университет се задават чрез редицата Pk = (Pk-1 * Ai + Bi) % M. За да може да генерирате по-бързо редиците е гарантирано, че M ще бъде точна степен на 2.
Изход
На стандартния изход изведете едно цяло число – търсения брой двойки.
Ограничения
  • 1 ≤ N ≤ 50
  • 1 ≤ Ci ≤ 1,000,000
  • 0 ≤ Fi, Ai, Bi < M ≤ 1,073,741,824
Примерен Вход Примерен Изход
3 8 3 2 5 2 6 0 3 0 4 3 7 3 5
7 128 42 18 33 66 13 76 17 15 666 3 54 10 17 122 90 121 1337 0 41 122 42 11 122 1 1 11 20 30 1059
В първия пример имената са {2, 4, 6, 0, 0, 0, 0, 0, 0, 3, 0, 3, 0}.
Мрън!