Sensenos laikos dzīvoja kāds karalis. Šis karalis mantojumā bija saņēmis kaklarotu, kas sastāv no N dārgakmeņiem, no kuriem M bija rubīni, bet pārējie - vienkāršāki dārgakmeņi. Karalis bija nolēmis kaklarotu pārdot dārglietu uzpircējam un par iegūto naudu iegādāties pāris zemes īpašumus skaistās vietās. Diemžēl izrādījās, ka dārglietu uzpircējs nav ar mieru pirkt visu kaklarotu, bet tikai tās fragmentus noteiktā garumā K. Par katru fragmentu samaksātās naudas daudzums bija atkarīgs no rubīnu daudzuma tajā. Ja fragmentā bija n (n≥0) rubīni, tad par šo fragmentu dārglietu uzpircējs bija ar mieru maksāt n2+1 dālderi. Par laimi N dalījās ar K bez atlikuma, tādēļ karalis nolēma sadalīt kaklarotu N/K fragmentos garumā K. Kopējais par kaklarotu iegūtais naudas daudzums varēja atšķirties atkarībā no tā, kurā vietā sākta kaklarotas sadalīšana fragmentos.
Tā, sadalot zīmējumā redzamo kaklarotu ar sešpadsmit dārgakmeņiem, no kuriem septiņi ir rubīni (iekrāsoti melnā krāsā), fragmentos pa četriem dārgakmeņiem, bija iespējami četri dažādi dalījumi:
Dalot kaklarotu, kā redzams variantos "A" un "B", varēja saņemt 21 dālderi, variantā "C" - 25, bet variantā "D" - 19 dālderus. Uzrakstiet programmu, kas dotam kaklarotas aprakstam un fragmenta garumam nosaka lielāko dālderu skaitu, kādu par šo kaklarotu bija iespējams iegūt!
Teksta faila rota.dat pirmajā rindā doti trīs naturāli skaitļi, kas atdalīti ar tukšumsimboliem - kaklarotas kopgarums N(N≤2*109), fragmenta garums K (K≤10000) un kaklarotā esošo rubīnu skaits M(M≤10000). N ir K daudzkārtnis. Katrā no nākošajām M faila rindām dots naturāls skaitlis robežās no 1 līdz N - kārtējā rubīna atrašanās vietas numurs (visi dārgakmeņi ir numurēti ar naturāliem skaitļiem no 1 līdz N pēc kārtas). Numuri failā ir doti augošā secībā.
Teksta faila rota.rez vienīgajā rindā jāizvada lielākais dālderu skaits, kādu bija iespējams dabūt par kaklarotu.
| rota.dat | rota.rez |
16 4 7 1 2 3 6 8 9 16 |
25 |