임프

어렵게 모은 금화를 들고 오래된 마법 상점에 들어섰다. 상점에는 신기한 물건이 n개 있고, 하나하나가 특별한 마법 상자 안에 잠겨 있다. i번 상자를 사려면 금화 $c_i$개를 내야 하고, 그 안에는 금화 $v_i$개 값어치의 물건이 들어 있다. 마법 도록을 읽고 통째로 외워 두었으므로 모든 상자의 값과 물건의 값어치를 이미 안다.

사람은 마법 물건을 한 개만 안전하게 지닐 수 있다. 그래서 가장 값진 물건 하나를 손에 넣는 것이 목표다. 임프라는 심술궂은 마법 생물만 아니었다면 그렇게 되었을 것이다.

임프는 마법 상자 속 물건을 쓸모없는 먼지로 바꾸는 주문을 걸 수 있다. 임프는 늘 상자를 산 직후에 주문을 걸어, 값은 치렀는데 물건은 얻지 못하게 만든다. 그러면 다른 상자를 사야 하고, 또 그다음 상자를 사야 한다.

임프가 주문을 거는 횟수는 많아야 k번이다. 물론 주문을 걸지 않고 물건을 그대로 가져가게 둘 수도 있다. 당신은 언제든지 빈손으로 상점을 나올 수 있다. 다만 물건을 하나 얻으면 그 물건을 지니고 상점을 떠나야 한다. 이익은 손에 넣은 물건의 값어치에서 그때까지 치른 금액을 모두 뺀 값이다. 당신은 이익을 가장 크게 하려 하고, 임프는 가장 작게 하려 한다. 둘 다 최선의 전략을 쓸 때 당신이 얻는 이익은 얼마인가?

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 테스트 케이스가 차례로 주어진다.

각 테스트 케이스의 첫 줄에는 물건의 개수 n ($1 \le n \le 150000$)과 임프가 주문을 거는 최대 횟수 k ($0 \le k \le 9$)가 주어진다. 다음 n개 줄 가운데 i번째 줄에는 i번 물건의 값어치 $v_i$와 상자의 값 $c_i$가 이 순서로 주어진다 ($0 \le v_i, c_i \le 1000000$).

각 테스트 케이스마다 당신이 얻는 이익을 한 줄에 출력한다.