Opis problema
 

Privatna brodska kompanija »TKO RADI, NE BOJI SE GLADI« dobila je na natječaju dozvolu za prijevoz tereta na udaljeni otok u južnoafričkom moru. Svaki pojedini teret je predstavljen s dvije komponente – veličinom i vrijednošću, a svakog tereta imamo neograničeno. Kako je put do otoka dugačak (a da bi stanovnici otoka bili sigurni da će barem netko od njih u svakom transportu dobiti ono što mu je neophodno), potrebno je uzeti barem jedan teret od svake pojedine grupe. Nakon takve selekcije utovara, a u slučaju da je preostalo još mjesta na brodu, treba popuniti brod sa bilo kojom količinom tereta, ali da ukupna vrijednost broda (s neophodnim teretom) bude najveća moguća.

Ulazni podaci
 

U prvom redu ulazne tekstualne datoteke TERET.IN nalaze se dva prirodna broja N (N <= 5000) i M (M <= 100) : N je veličina broda, a M je broj različitih tereta. U narednih M redova nalaze se parovi brojeva T (T <= 100) i V (V <= 1000) : T je veličina tereta, a V njegova vrijednost.

Izlazni podaci
 

U prvi i jedini redak izlazne tekstualne datoteke TERET.OUT treba ispisati ukupnu vrijednost tereta na brodu.

Napomena
 

Od podataka zadanih u datoteci sigurno će se moći naći rješenje.

Primjeri:
 

TERET.IN   21 3   5 10   7 13   8 11	TERET.IN   55 5   3 4   4 5   7 10   8 11   9 13
TERET.OUT   34	TERET.OUT   77