| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Bit koristab oma riidekappi, kus tal on hulk programmeerimisvõistluste T-särke. Särgid on mitmel riiulil erineva kõrgusega virnades.
Bit on juba lapsest saadik armastanud suurima ühisteguriga seotud mänge ja otsustas paigutada särgid riiulitele nii, et kui ta vaatab virnades olevate särkide arve, leiab iga riiuli jaoks nende arvude suurima ühisteguri ja liidab siis nende ühistegurite väärtused kokku, on tulemus maksimaalne võimalik.
Näiteks kui tal on esimesel riiulil ühes virnas 6 ja teises 9 särki, teisel riiulil ainult üks 2 särgiga virn ja kolmandal riiulil kolm virna vastavalt 5, 6 ja 7 särgiga, siis on otsitav summa $\gcd(6, 9) + \gcd(2) + \gcd(5, 6, 7) = 3 + 2 + 1 = 6$.
Muidugi sai Bit kohe aru, et maksimaalse summa saamiseks tuleks iga särgivirn eraldi riiulile panna. See oleks aga liiga lihtne ja et mäng oleks põnevam, otsustas ta, et igal riiulil peab olema kas vähemalt $D$ virna või peab riiul olema täiesti tühi (ja tühja riiuli suurim ühistegur on 0ドル$).
Lisaks ei taha Bit oma särkide järjekorda liiga palju muuta, sest need on tal võistluste ja aastate kaupa sorteeritud. Sellepärast tõstab ta särke ümber ainult järgmise reeglite kohaselt:
Kirjutada programm, mis leiab maksimaalse ühistegurite summa, mille Bit saavutada võib, kui tal on palju aega ja ta võib särgivirnu ühelt riiulilt teisele tõsta kuitahes palju kordi.
Tekstifaili esimesel real on riiulite arv $N,ドル särgivirnade koguarv $M$ ja mitte\-tühja riiuli virnade arvu miimimum $D$ (1ドル \le D \le M \le N \le 500,000円$).
Järgmisel $N$ real on riiulite kirjeldused. Iga rea alguses on riiulil olevate särgivirnade arv $K_i$ (0ドル \le K_i \le M$) ja selle järel $K_i$ täisarvu $X_{i,j}$ (1ドル \le X_{i,j} \le 10^9$), mis näitavad, mitu särki igas virnas on. Riiulite kirjeldused on antud ülalt alla ja virnade kirjeldused vasakult paremale.
Tekstifaili ainsale reale väljastada üks täisarv: maksimaalne ühistegurite summa, mille Bit saavutada võib.
3 3 1 0 2 1 3 1 2
6
Kapis on 3 riiulit ja neil kokku 3 virna särke. Bit võib iga särgivirna eraldi riiulile panna ja seega saada ühistegurite summaks 1ドル + 3 + 2 = 6$.
6 5 2 2 4 8 1 1 0 0 0 2 3 6
5
Bit tahab jätta igale mittetühjale riiulile vähemalt kaks särgivirna. Ta võiks panna kõik 5 virna ühele riiulile ja saada ainsaks ühisteguriks 1ドル$. Ta võib panna 4, 8 ja 1 särgiga virnad ühele ning 3 ja 6 särgiga virnad teisele riiulile ning saada ühistegurite summaks 1ドル + 3 = 4$. Aga ta võib panna ka 4 ja 8 särgiga virnad ühele ning 1, 3 ja 6 särgiga virnad teisele riiulile ning saada ühistegurite summaks 4ドル + 1 = 5$.