Mirunei îi plac numerele întregi şi cărţile de joc. Într-o bună zi, pentru că se plictisea, s-a decis să inventeze un joc pentru o singură persoană. Şi-a luat pachetul de cărţi preferat şi a scris pe fiecare faţă a fiecărei cărţi câte un număr întreg. Apoi a înşirat toate cele N cărţi din pachet pe masă şi a stabilit regulile jocului:
Fiecare carte poate fi pusă cu oricare dintre cele două feţe în sus.
După ce aşează toate cărţile pe masă, acestea trebuie împărţite în două mulţimi: una de cardinal K, iar cealaltă de cardinal N-K.
Se adună valorile vizibile înscrise pe cărţile din prima mulţime, cea de cardinal K, şi se scad cele de pe cărţile din a doua mulţime.
Se doreşte maximizarea valorii obţinute.
Cerinţă
Ştiind valorile înscrise pe cărţile de joc, ajutaţi-o pe Miruna să afle răspunsul căutat.
Date de intrare
Fişierul de intrare sumdif.in conţine pe prima linie două numere întregi N şi K, având semnificaţia din enunţ. Fiecare dintre următoarele N linii va conţine câte două numere întregi, reprezentând valorile înscrise pe cele două feţe ale unei cărţi.
Date de ieşire
Fişierul de ieşire sumdif.out va conţine o singură linie pe care va fi scris un singur număr întreg, reprezentând valoarea maximă pe care o poate obţine Miruna în jocul de mai sus.
Restricţii
1 ≤ N ≤ 1000
0 ≤ K ≤ N
Valorile înscrise pe cărţile de joc vor fi din intervalul [-1000, 1000].
Exemplu
sumdif.in
sumdif.out
Explicatie
4 2
-5 4
9 -4
1 2
0 -10
26
Miruna va pune a doua şi a treia carte în prima mulţime