Pentru desfăşurarea jocului se utilizează k seturi de câte n+2 bile. Dintre cele n+2 bile:
- n sunt inscripţionate cu numerele distincte de la 1 la n, reprezentând valoarea fiecărei bile;
- două bile sunt inscripţionate cu numărul 0, au un rol special şi nu au valoare.
La joc participă k jucători, numerotaţi cu numerele distincte de la 1 la k.
Jocul se desfăşoară astfel:
- din primul set de bile, primul jucător primeşte p bile pe care trebuie să le aranjeze, în linie, astfel încât numerele inscripţionate pe aceste bile să formeze o secvenţă de valori consecutive şi de sumă maximă;
- din al doilea set de bile, al doilea jucător primeşte p bile pe care trebuie să le aranjeze, în linie, astfel încât numerele inscripţionate pe aceste bile să formeze o secvenţă de valori consecutive şi de sumă maximă;
- ...
- din al k-lea set de bile, al k-lea jucător primeşte p bile pe care trebuie să le aranjeze, în linie, astfel încât numerele inscripţionate pe aceste bile să formeze o secvenţă de valori consecutive şi de sumă maximă;
- o secvenţă poate conţine bile cu valoarea 0 ce pot înlocui orice valoare nenulă, fără a modifica suma valorilor din secvenţă.
Câştigă jucătorul care obţine secvenţa cu suma valorilor bilelor maximă, aceasta numindu-se suma câştigătoare.
Cerinţă
Scrieţi un program care să citească numărul n, numărul k, valorile bilelor primite de fiecare jucător, şi care să determine numărul câştigătorul jocului, precum şi valoarea sumei câştigătoare.
Date de intrare
Prima linie a fişierului joc18.in conţine trei numere, n k p, separate prin câte un spaţiu, cu semnificaţia din enunţ. Fiecare din următoarele k linii (în ordinea crescătoare a numerelor jucătorilor) conţine câte p numere naturale, separate prin câte un spaţiu, reprezentând valorile bilelor primite de fiecare jucător.
Date de ieşire
Prima linie a fişierului joc18.out va conţine două numere naturale, separate printr-un un spaţiu. Prima valoare reprezintă numărul câştigătorului jocului. A doua valoare reprezintă suma câştigătoare.
Restricţii
• 1 ≤ n ≤ 500000
• 1 ≤ k ≤ 20
• 1 ≤ p ≤ min(100000,n+2)
• Se garantează că fiecare jucător primeşte bile cu valori distincte, cu excepţia bilelor speciale.
• Dacă suma câştigătoare este obţinută de mai mulţi jucători, jucătorul câştigător va fi jucătorul cu numărul cel mai mic.
Exemple
joc18.in
joc18.out
Explicaţii
6 3 5
5 1 6 3 2
6 1 3 4 0
2 0 6 4 0
2 13
La joc participă 3 jucători; fiecare primeşte câte 5 bile, valorile acestora fiind între 1 şi 6.
Primul jucător nu are bile speciale. El poate construi secvenţa cu suma maximă 11 şi anume: 5 6. Al doilea jucător are o bilă specială. El poate construi secvenţa cu suma maximă 13 şi anume: 3 4 0 6. Al treilea jucător are două bile speciale. El poate construi secvenţa cu suma maximă 12 şi anume: 2 0 4 0 6. Suma câştigătoare este 13 şi este obţinută de jucătorului 2.