Am un client bogat, pasionat de maşini de epocă. Azi mi-a cerut să achiziţionez K maşini pentru colecţia sa. Ca urmare am realizat o listă care conţine N maşini pe care am reuşit să le găsesc disponibile pe piaţa maşinilor de epocă. Pentru fiecare maşină am specificat costul, precum şi valoarea de colecţie a acesteia (estimată pe baza vechimii, mărcii, stării de funcţionare, configuraţiei, etc, conform standardelor internaţionale şi exprimată sub forma unui număr natural).
Clientul meu doreşte să achiziţioneze K maşini dintre cele N astfel încât valoarea totală de colecţie a acestora să fie maximă. Dar evident, doreşte să facă acest lucru cu cât mai puţini bani.

Cerinţă

Scrieţi un program care alege K maşini dintre cele N din listă, astfel încât valoarea totală de colecţie a maşinilor selectate să fie maximă, iar suma cheltuită pentru a obţine această valoare de colecţie maximă să fie cât mai mică.

Date de intrare

Fişierul de intrare vintage.in conţine pe prima linie numerele naturale N K, reprezentând numărul de maşini din listă, respectiv numărul de maşini ce urmează să fie achiziţionate. Urmează N linii, câte o linie pentru fiecare maşină. Pe a i-a linie dintre cele N (1≤i≤N) se află două numere naturale separate prin spaţiu cost valoare, reprezentând costul maşinii, respectiv valoarea de colecţie a acesteia.

Date de ieşire

Fişierul de ieşire vintage.out va conţine o pe prima linie două numere naturale separate prin spaţiu vmax cmin, reprezentând valoarea totală maximă a maşinilor selectate, respectiv costul total minim necesar pentru a achiziţiona cele K maşini de valoare de colecţie maximă. Pe cea de a doua linie se află K numere naturale distincte, cuprinse între 1 şi N, separate prin câte un spaţiu, reprezentând maşinile achiziţionate.

Restricţii

• 0 < N ≤ 1000
• 1 ≤ K ≤ N
• Costurile şi valorile de colecţie ale maşinilor sunt numere naturale ≤1000000.
• Maşinile sunt numerotate de la 1 la N, în ordinea din fişierul de intrare.
• Ordinea în care afişaţi maşinile selectate în fişierul de ieşire nu contează.
• Se acordă 50% din punctajul/test pentru determinarea valorii vmax; 60% din punctaj se acordă pentru determinarea valorilor vmax şi cmin; punctajul se acordă integral pentru rezolvarea tuturor celor 3 cerinţe.

Exemple

vintage.in	vintage.out	Explicaţii
6 3 100000 100 210000 220 200000 250 180000 200 120000 200 110000 100	670 530000 2 3 5	Vor fi achiziţionate maşinile 2 3 5, care au valoare de colecţie totală maximă: 250+220+200=670 şi costul total minim (pentru valoarea de colecţie maximă) 210000+200000+120000=530000

autor: Prof. Emanuela Cerchez

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com