Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-12-25 15:10:49.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:placute.in, placute.outSursăInfoarena Monthly 2012, Runda 11
AutorMihai-Alexandru Dusmanu, Teodor PlopAdăugată deTeodor94Teodor Plop Teodor94
Timp execuţie pe test0.1 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Placute

Cu ocazia sarbatorilor de iarna, Flamanzila se gandeste ca ar fi momentul sa fure niste porci pentru a isi potoli foamea. Asadar, el gaseste in curtea lui Ionel N porci. Fiecare porc are o placuta de o anumita culoare pe care este inscriptionat numarul de kilograme al acestuia.

Pentru a se asigura ca Ionel nu observa lipsa porcilor, Flamanzila nu va fura niciodata doi porci consecutivi cu aceeasi culoare a placutei.

De fiecare data cand va veni la furat, Flamanzila va fura cel mai gras porc pe care il va putea fura respectand conditia de mai sus.

Sa se spuna care este greutatea totala maxima pe care o poate fura Flamanzila, stiind numarul total de porci N si numarul maxim de culori folosite pentru coloararea placutelor K.

Date de intrare

În fişierul de intrare placute.in se vor gasi pe prima linie numerele naturale N si K. Pe urmatoarele N linii se vor gasi cate 2 numere naturale g[i] si c[i], reprezentand datele porcului i - numarul de kilograme si culoarea placutei i.

Date de ieşire

În fişierul de ieşire placute.out se va gasi un singur numar natural, reprezentand greutatea maxima pe care o poate fura Flamanzila.

Restricţii

  • 1 ≤ N ≤ 100000
  • 1 ≤ K ≤ 1000
  • 1 ≤ a[i] ≤ 1000
  • 1 ≤ c[i] ≤ K

Exemplu

placute.inplacute.out
6 3
5 1
4 1
1 3
2 2
5 2
3 2
20

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?