Fisierul cheltuieli.in are cel mult 10^6 linii, fiecare linie continand cate trei numere naturale din intervalul [1,10^2], reprezentand, in aceasta ordine, date despre cate o achizitie: tipul produsului cumparat, numarul de produse de acest tip cumparate, respectiv pretul unui astfel de produs la acel moment. Numerele aflate pe aceeasi linie sunt separate prin cate un spatiu.
Se cere sa se afiseze pe ecran cea mai mare suma cheltuita pentru toate produsele de acelasi tip, precum si numarul de tipuri de produse pentru care s-a obtinut aceasta suma. Proiectati un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: daca fisierul cheltuieli.in are continutul 4 1 10 1 16 1 4 2 8 2 1 5 1 5 2 se afiseaza pe ecran: 26 2 (s-a cheltuit suma maxima 26 pentru produsele de tipul 1 si 4: 26=161+52=110+28)
- Date de intrare
- Fisierul cheltuieli.in: pe fiecare linie, tip, cantitate, pret.
- Date de iesire
- Se afiseaza suma maxima cheltuita pentru un tip de produs, urmata de numarul de tipuri care ating acest maxim, separate printr-un spatiu.
- Restrictii
- cel mult 10^6 linii, tip/cantitate/pret in [1, 100]
Exemple
Exemplul 1
Intrare
4 1 10 1 16 1 4 2 8 2 1 5 1 5 2
Iesire
26 2
Exemplul 2
Intrare
1 1 1
Iesire
1 1