Liceul Naţional Anonim (LNA) este invitat să participe la olimpiada de matematică-română cu o echipă formată din m elevi. La această olimpiadă elevii lucrează în echipă şi trebuie să rezolve două subiecte: unul de română şi altul de matematică.
Au fost testaţi şi punctaţi la cele două materii n elevi, numerotaţi de la 1 la n. Aşa cum era de aşteptat, în general, elevii buni la matematică s-au dovedit cam slăbuţi la română şi viceversa.
Pentru a maximiza şansele de câştig ale echipei LNA, directorul a decis să trimită m elevi dintre cei n elevi testaţi, astfel încât diferenţa în modul dintre suma punctajelor de la limba română ale elevilor din echipă şi suma punctajelor la matematică ale elevilor din echipă să fie minimă. Dacă există mai multe echipe de elevi care îndeplinesc condiţia precedentă, va fi selectată dintre acestea o echipă pentru care suma tuturor notelor să fie maximă.
Cerinţă
Scrieţi un program care să determine în conformitate cu decizia directorului, diferenţa în modul dintre suma punctajelor de la limba română ale elevilor din echipa LNA şi suma punctajelor la matematică ale elevilor din echipă, precum şi suma tuturor punctajelor elevilor din echipa LNA.
Date de intrare
În fişierul de intrare materom.in se află pe prima linie numerele naturale n şi m separate printr-un spaţiu, având semnificaţia din enunţ.
Pe fiecare dintre următoarele n linii se află două numere naturale separate printr-un spaţiu. Mai exact, linia i din fişier (i=2, n+1) conţine mi ri, unde mi este punctajul obţinut la matematică, iar ri este punctajul obţinut la limba română de elevul i-1.
Date de ieşire
Fişierul de ieşire materom.out conţine două linii. Pe prima linie se va afişa diferenţa (în modul) dintre suma punctajelor de la limba română ale elevilor din echipă şi suma punctajelor la matematică ale elevilor din echipă. Pe cea de a doua linie se va afişa suma punctajelor elevilor selectaţi în echipa LNA.
Restricţii
1 ≤ m < 20
1 ≤ n ≤ 500
m ≤ n
0 ≤ mi, ri ≤ 20
Exemple
materom.in
materom.out
Explicaţii
4 2
2 3
1 2
6 2
4 1
2
10
Dintre cei 4 elevi trebuie să selectăm 2. Avem 6 posibilităţi, dintre care 3 au diferenţa (în modul) dintre suma notelor la matematică şi suma notelor la română 2.
Acestea sunt:
– (1, 2) pentru care suma punctajelor este 8
–(1, 4) pentru care suma punctajelor este 10
–(2, 4) pentru care suma punctajelor este 8.
Alegem combinaţia 1 4 deoarece are suma maximă.