34710번 - 원빈이의 인생 스케줄링

문제

원빈이는 자신의 완벽한 인생을 살기 위해 지식($K$)과 건강($H$)이라는 두 가지 수치를 관리한다. 1ドル$일차 아침에 두 수치는 모두 0ドル$이며, 원빈이는 1ドル$일차부터 매일 아침 두 가지 수치 중 하나를 선택해 그 값을 1ドル$ 증가시킬 수 있다.

원빈이의 인생에는 $N$개의 작업이 주어지고, 원빈이는 $N$개의 작업을 모두 문제 없이 수행하여 행복 수치 $S$를 최대화하고 싶어 한다. $i$번째 작업은 $T_i$일 저녁에 수행되는데, 그 시점에 원빈이의 지식 수치 $K$가 해당 작업의 요구치 $L_i$보다 크거나 같다면 원빈이의 행복 수치 $S$에 현재 건강 수치 $H$만큼이 더해진다. 만약 $K$가 $L_i$보다 작다면 원빈이의 완벽한 인생은 무너져 행복 수치는 영원히 $-1$로 고정된다.

1ドル$일차 아침에 행복 수치 $S$는 0ドル$이다. 원빈이가 최적으로 행동했을 때, 마지막 작업이 정산된 직후 행복 수치 $S$의 최댓값을 구해주자.

입력

첫째 줄에 작업의 개수를 나타내는 정수 $N$이 주어진다. $(1 \le N \le 200,000円)$

둘째 줄부터 $N+1$번째 줄까지 각 줄마다 두 정수가 주어진다. 두 정수는 각 작업의 마감일 $T_i$와 지식 요구랑 $L_i$를 뜻한다. $(1 \le T_i \le 200,000円; 0 \le L_i \le 200,000円)$

출력

마지막 작업이 정산된 직후 행복 수치 $S$의 최댓값을 출력한다. 만약 모든 요구 조건을 만족하는 것이 불가능하다면 -1을 출력한다.

제한

노트