Problem

Arman loves eating cakes. It's good for him that it's the cake festival and every shop in city is selling cakes. He wants to have a delicious cake, at as low price as possible.

He lives in a linear city where his house is at point 0 followed by shops on each point with distance between consequtive points exactly 1 meter. Also, it takes exactly 1 minute to reach from a point to another. Initially, he is at his house. There are n shops in total, numbered 1 to n. The ith shop is at a distance of i meters from his house. The ith shop sells cakes at a price of P[i], and has a stock of S[i] cakes initially.

Since everybody wants to taste the delicious cakes, at every 5th minute the stock of every shop is decreased by k units. Arman can buy the cake from a shop only if atleast 1 cake still remains. Calculate the minimum price at which Arman can buy the cake and satisfy his cravings.

Input Format

• The first line contains an integer T - number of test cases.
• First line of each test case contains two integers - n and k.
• n lines follows. The ith line contains two integers - P[i] and S[i].

Output Format

For each test case, print an integer - the minimum price at which Arman can buy a cake.

Constraints

• 1 <= T <= 10^5
• 1 <= n, k <= 10^5
• 1 <= P[i], S[i] <= 10^9
• Sum of n over all testcases does not exceed 2*10^5.

Sample Input 0

1
7 5
10 2
9 3
10 4
10 5
6 4
1 4
7 8

Sample Output 0

7

Explanation

Shop 1: stock is 2 units. Arman can buy the cake at 10.

Shop 2: stock is 3 units. Arman can buy the cake at 9.

Shop 3: stock is 4 units. 9 is a better option.

Shop 4: stock is 5 units. 9 is still a better option.

Shop 5: stock has become 0 as Arman reaches the shop at 5 minutes, just after the stock decreases. So, he can't buy from here.

Shop 6: stock has become 0

Shop 7: stock still remains Arman can buy at 7(which is the minimum cost).