Sphinx cultural fest of MNIT is organizing a competition "Find The Infinity-Stones"
N students took part in this competition.There were M stones which were hidden at different spots in MNIT.After the competition was over , each stone was with one of the student and no stone was left unspotted. i.e. each stone is possesed by any one of the student.Some students may have zero stones. Assume M stones are different and the ith type of stone is possessed by exactly one student (1<=i<=M).
The student having max stones was the winner.Although students were told they can't exchange stones with one another.It was strictly mentioned.But Student no. 1 doesn't gave a damn to it and decided to cheat. Assume only STUDENT no.1 cheated and no one else.
So he decided to win the competition and for that he should strictly have greater stones than any one else. So he decided to take stones from other students in order to win but they were charging some money in return.
Note that student no 1 won't cheat if he is already winning the competition. So Student no. 1 wants to win the competition .Calculate the minimum cost for this.
Input:-
You are given n,m denoting the number of students and the number of stones repectively. Next m lines contains two numbers x[i] and y[i] which means that ith stone is possessed by x[i]th student and would charge y[i] amount if student no. 1 wants ith stone.
Index of the student cheating is always 1.
1<= n,m <=3000
1<=x[i]<=n
1<=y[i]<=10^9
Output:-
Print the minimum amount required for Student 1 to win the competition.
Student 1 would buy stones from student no. 2 and student no. 5. From 2nd student cost would be 100 and from 5th student cost would be 400, so total cost would be 500. And then 1st student would be having max stones .
