Fişierul intrare/ieşire:kbetray.in, kbetray.outSursăAlgoritmiada 2016 Runda 1 Juniori
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

KBetray

La un concurs de patinaj artistic in stil valoros, cei 2 * N participanti s-au hotarat sa participe in perechi de cate 2, formand astfel N echipe. Pentru fiecare participant se stie valoarea lui. Valoarea unei echipe este definita ca maximul valorii dintre cei 2 (din moment ce e lucru in echipa, doar participantul mai valoros e important). Initial, toti participantii au fost repartizati cu cate un partener, si desigur, nu toata lumea este multumita. Din moment ce concursul este in stil valoros, un sistem de tradare a fost impus. Orice participant poate sa isi tradeze partenerul si sa il schimbe cu oricare alt participant.

Valoare concursului este egal cu suma valorilor fiecarei echipe. Scopul vostru este sa determinati valoarea maxima a concursului stiind ca se pot efectua maxim K tradari.

Date de intrare

Fişierul de intrare kbetray.in va contine pe prima linie 2 numere naturale N si K. Pe urmatoarele N linii vor fi cate 2 numere reprezentand valorile celor 2 participanti din echipa i.

Date de ieşire

Fişierul de ieşire kbetray.out va contine un singur numar natural reprezentand valoarea maxima a concursului.

Restricţii

  • 1 ≤ N,K ≤ 100.000
  • Valorile participantilor sunt numere naturale din intervalul [0, 1.000.000.000]

Exemplu

kbetray.inkbetray.out
6 2
8 10
3 2
1 5
13 7
0 3
2 2
46
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?