31267번 - 시간 외 근무 멈춰!!! 서브태스크

문제

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

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

후임병까지도 시간 외 근무를 해야 한다는 사실이 마음 아팠던 준민이는, 간부님 몰래 작업들의 데드라인을 조작하고자 한다. 데드라인을 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円$
• $d_i \neq d_j$; 1ドル\le i < j \le N$
• 모든 입력은 정수이다.

서브태스크

힌트