문제
당신은 신비하고 희귀한 마법 아이템을 사기 위해 희귀한 황금을 들고 Ye Olde Magic Shoppe에 도착했다. 가게에는 n개의 아이템이 있고, 각각은 잠겨있는 특별한 마법 상자에 담겨 있다. i번째 상자를 사는데 ci개의 금조각이 필요하며, 금조각 vi만큼의 가치를 가지고 있다. 이미 Ye Olde Magic Catalogue를 읽고, 완벽하게 기억해낸 당신은, 모든 아이템의 가격과 가치를 알고 있다.
모든 필멸자는 단 하나의 마법 아이템만을 가지고 가게에서 나갈 수 있다. 때문에 당신은 가게에서 가장 비싼 아이템을 목표로 한다. 그리고 실제로 얻을 수도 있었을 것이다. 임프라고 알려진 장난기 충만한 마법 생물만 없었다면…
임프는 장난스러운 주문을 외는데, 이 주문은 어떤 마법 상자 하나의 내용물을 가치 없는 모래로 바꾼다. 물론, 임프는 당신이 마법 상자를 사고, 돈을 지불했지만 가지지는 못하게 하기 위해, 주문을 외울 것이다. 여러분은 어쩔 수 없이 다음 상자를 사야 하고, 다음 상자도…
임프는 k번만 주문을 외울 수 있다. 그는 물론, 나중을 위해 여러분이 아이템을 가지도록 놔둘 수도 있다. 여러분은 언제든 빈 손으로 가게를 떠날 수 있다(물론 매우 불명예스러운 행동이다). 하지만, 한 번이라도 아이템을 가졌다면, 당신은 무조건 그 아이템을 들고 가게를 나와야 한다. 당신은 얻는 이득(얻은 아이템에서 지불한 가격을 뺀 값)을 최대로 하려 하고, 임프는 당신의 이득을 최소로 하고 싶어 한다. 만약 둘 모두 최선의 선택을 했다면, 당신이 얻는 이득은 얼마인가?
입력
첫 번째 줄에 테스트케이스의 개수 T가 주어진다. 각 테스트케이스는 아래와 같이 주어진다.
첫 번째 줄에 아이템의 수 n (1 ≤ n ≤ 150,000)과 임프가 쓸 수 있는 주문의 최대 횟수 k (0 ≤ k ≤ 9)가 주어진다.
다음 n개의 줄에는 각 아이템의 가치 vi와 판매 가격 ci가 주어진다. (0 ≤ vi, ci ≤ 106).
출력
첫 번째 줄에 당신이 얻을 수 있는 이득을 출력한다.
예제
1
3 1
10 5
8 1
20 12
7
로그인해야 코드를 작성할 수 있어요.