시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 181 | 28 | 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$의 피해를 입는다. 이것보다 좋게 할 수 없다.