시간 외 근무 멈춰!!!

시간 제한1초메모리 제한1024 MB

요약

각 업무의 마감일과 작업량이 주어질 때, 마감일을 최대 K번 하루씩 뒤로 미뤄 필요한 야근 시간을 최소로 구하는 문제입니다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 힙
정답자: 아직 제출이 없습니다

문제

전역 전까지 시간 외 근무에서 벗어나지 못한 준민이는 결국 전역을 앞두고 남은 일들을 후임병 민욱이에게 넘겨주고 말았다. 민욱이가 넘겨받은 작업은 총 $N$ 개이며, 작업 $i$ 에는 $t_i$ 만큼의 작업량이 필요하고 데드라인은 $d_i$ 일이다. 넘겨받은 작업들 중 데드라인이 같은 작업은 없다.

민욱이의 근무는 월요일부터 시작한다. 평시 근무는 월요일부터 금요일까지만 하고, 시간 외 근무는 모든 요일에 할 수 있다. 평시 근무와 시간 외 근무는 각각 하루에 최대 한 번씩 진행할 수 있으며, 진행할 때마다 원하는 작업 하나를 골라 작업량 1을 처리할 수 있다.

준민이는 간부님 몰래 작업들의 데드라인을 조작하려고 한다. 데드라인을 한 번 조작하면 원하는 작업의 데드라인을 1일 늘릴 수 있으며, 들키지 않도록 최대 $K$ 번까지만 조작하려고 한다. 준민이가 데드라인을 조작했다는 사실을 간부님께 들키지 않기 위해, 민욱이는 모든 작업을 원래 데드라인이 빠른 순서대로 완료하기로 했다.

데드라인을 최대 $K$ 번 조작했을 때, 민욱이가 해야 하는 최소 시간 외 근무 시간을 구하시오.

입력

첫 번째 줄에 작업 개수 $N$ 과 데드라인 조작 횟수 $K$ 가 공백으로 구분되어 주어진다. 이후 $N$ 개의 줄에 걸쳐 $i+1$ 번째 줄에 $i$ 번째 작업의 데드라인 $d_i$ 와 작업량 $t_i$ 가 공백으로 구분되어 주어진다.

출력

데드라인을 최대 $K$ 번 이하로 조작한 경우 민욱이가 해야 하는 최소 시간 외 근무 시간을 출력한다. 어떻게 해도 시간 내에 작업을 끝낼 수 없다면 -1을 출력한다.

제한

$1 \le N \le 200\,000$ , $0 \le K \le 10^9$ , $1 \le d_i \le 200\,000$ , $1 \le t_i \le 200\,000$ , $1 \le i < j \le N$ 일 때 $d_i \neq d_j$ 이다. 모든 입력은 정수이다.

예제2

예제 1
입력
```
5 5
2 1
8 3
6 1
7 4
10 1
```
예상 출력
```
1
```
예제 2
입력
```
3 0
5 3
3 5
4 3
```
예상 출력
```
-1
```