joc

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
• $2$ sunt inscripţionate cu numărul $0$, care 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 suma 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 suma maximă;
• $\dots$
• 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 suma 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 joc.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 joc.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 și precizări

• $1 \leq n \leq 500 \ 000$
• $1 \leq k \leq 20$
• $1 \leq p \leq min(100 \ 000, 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.
• Pentru determinarea corectă a numărului jucătorului câştigător se acordă $40\%$ din punctaj.
• Pentru determinarea corectă a sumei câştigătoare se acordă $60\%$ din punctaj.

Exemplu

joc.in

6 3 5
5 1 6 3 2 
6 1 3 4 0 
2 0 6 4 0 

joc.out

2 13

Explicație

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$.