| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 303 | 30 | 2 | 3.448% |
야수들의 겨울 숲 습격이 시작되었다. 이를 맞아 겨울 숲의 수호자는 숲 상공에서 야수들에게 마법 화살을 쏘아 겨울 숲을 지키고자 한다.
습격이 시작된 시점부터 매 초마다 다음의 사건들이 순서대로 일어난다.
수호자는 야수가 언제 어디서 생성될지 미리 알고 있으며, 이를 바탕으로 매 초마다 어떤 야수를 쏠지 전략을 잘 세우면 숲이 입는 피해를 줄일 수 있다.
예를 들어, 습격이 시작된 시점의 0ドル$초 후에 20ドル$만큼 떨어진 위치에서 야수 1이 등장하고, 1ドル$초 후에 14ドル$만큼 떨어진 위치에서 야수 2가 등장하고 $K = 10$이라고 가정하자. 이 때 수호자가 야수 1을 0ドル$초부터 10ドル$번 공격하고 야수 2를 10ドル$초부터 10ドル$번 공격한다면, 야수 1은 겨울 숲에 다가오기 전에 죽지만 야수 2는 15ドル$초부터 겨울 숲을 공격하기 시작해서 19ドル$초까지 숲을 파괴하고 죽으므로 겨울 숲은 5ドル$의 피해를 입는다.
하지만 야수 1을 0ドル$초부터 1ドル$번, 야수 2를 1ドル$초부터 10ドル$번, 야수 1을 다시 11ドル$초부터 9ドル$번 공격하면 겨울 숲이 피해를 입지 않은 채로 모든 야수를 쓰러트릴 수 있다.
이 때 이러한 전략은 (시작 시간, 공격 횟수, 야수의 번호)로 나타내어지는 사건들이 시간 순서로 정렬된 집합으로 표현할 수 있다. 위의 예시에서 첫 번째 전략은 $(0, 10, 1),ドル $(10, 10, 2)$로, 두 번째 전략은 $(0, 1, 1),ドル $(1, 10, 2),ドル $(11, 9, 1)$로 표현할 수 있다.
당신의 목적은 수호자를 도와 겨울 숲의 피해를 최소화하면서 모든 야수를 쓰러트리는 전략을 찾는 것이다.
첫 줄에 테스트 케이스의 수인 $T$ (1ドル \leq T \leq 2,000$)이 주어진다.
각 테스트 케이스의 첫 줄에는 야수들의 수인 $N$ (1ドル \leq N \leq 10,000$)과 야수 하나를 쓰러트리기 위해 쏴야 하는 화살의 수인 $K$ (1ドル \leq K \leq 100,000$)이 주어진다.
다음 $N$개의 줄에 $i$번째 야수가 생성되는 시간인 $a_{i}$과 위치인 $b_{i}$ (0ドル \leq a_{i}, b_{i} \leq 10^{9}$)가 주어진다.
모든 테스트 케이스들의 $N$의 합은 10,000ドル$을 넘지 않음이 보장된다.
각 테스트 케이스에 대해 수호자가 세운 최적의 전략을 다음과 같이 출력한다.
첫 줄에는 겨울 숲이 입는 총 피해의 최소값을 출력한다.
다음 줄에는 수호자가 세운 전략을 표현하는 사건의 개수 $M$ ($N \leq M \leq 10 \times N$)을 출력한다. 입력의 모든 경우에 대해, 이러한 사건의 개수가 10ドル \times N$을 넘지 않는 전략이 항상 존재함이 보장된다.
다음 $M$개의 줄에는 사건의 시작 시간인 $L,ドル 시작 시간부터 연속해서 같은 야수를 공격한 횟수인 $D$와 공격한 야수의 번호인 $j$를 한 줄씩 시간 순서로 출력한다. (0ドル \leq L \leq 10^{14},ドル 0ドル < D \leq K,ドル 1ドル \leq j \leq N$)
가능한 방법이 여럿일 경우 그 중 아무거나 출력한다.
2 2 10 0 20 1 14 2 10 1 14 5 15
0 3 0 1 1 1 10 2 11 9 1 1 2 1 10 1 11 10 2
첫 번째 테스트 케이스의 경우, 첫 번째 야수를 0ドル$초부터 1ドル$번 공격하고 두 번째 야수를 1ドル$초부터 10ドル$번 공격하고 첫 번째 야수를 11ドル$초부터 9ドル$번 공격하면 된다.
두 번째 테스트 케이스의 경우, 첫 번째 야수를 1ドル$초부터 10ドル$번 공격하고 두 번째 야수를 11ドル$초부터 10ドル$번 공격하면, 두 번째 야수는 20ドル$초부터 숲을 공격할 수 있으므로 숲은 1ドル$의 피해를 입는다. 이것보다 좋게 할 수 없다.