1048:We don't match each other

01 has a crush on n girls.He will to show his love for they,but every girl might say "We don't match each other".Every girl might say this sentence is greater than or equal to once.Every time will cause harm to him.Question, he can hear a few times at most?

Input t representation has t (1<=t<=20) group data.

The first line of the input data in each group two number n, m, n (1 < = n < = 100) on behalf of the total number of girls, m (1 < = m < = 100000) on behalf of 01 can withstand the most damage

Then n lines, each line has two digital c, h represents this girl said to him for c times (1 < = c < = 10), and will cause h damage to him.(50< =  h < = 10000)

He heard at most a few times.

1

2 200

5 100

10 10

15