RedTok ShortReels

이미지 출처: commons.wikimedia.org

Jarmína는 Rauðtifa Stuttkefli 앱을 꽤 많이 사용한다. 이 앱이 그녀의 시간을 너무 많이 차지하기 시작했고, 앱에서 얻는 도파민에 너무 중독된 나머지, 앱에서 얻는 도파민을 최대화할 방법을 찾기 위해 아이슬란드 알고리즘 문제 해결 학회에 연락했다.

프로그램은 정해진 순서대로 동영상을 보여 준다. 각 동영상에는 밀리초 단위로 주어진 특정 길이 $L_i$와, 그 동영상을 시청하면 얻는 도파민의 양 $D_i$가 있다. 동영상 하나를 건너뛰는 데는 $k$밀리초가 걸린다. 동영상의 일부만 시청해서는 도파민을 얻지 못한다.

이제 그녀가 얻는 도파민을 최대화할 수 있도록 동영상을 시청하는 최선의 방법을 찾아 주는 프로그램이 필요하다.

그녀를 도와줄 수 있는가?

시간이 다 떨어지는 경우가 아니라면, 각 동영상을 끝까지 시청하거나 $k$밀리초를 사용하여 건너뛰어야 한다.

채점

그룹 | 점수 | 제약 조건

1 | 10 | $n = 1$.

2 | 20 | $n \leq 20$.

3 | 35 | $k = 0$.

4 | 35 | 추가 제약 조건 없음.

입력의 첫째 줄에는 두 정수 $n, k$가 주어지며, 각각 동영상의 개수와 동영상 하나를 건너뛰는 데 걸리는 밀리초 수를 나타낸다. 항상 $1 \leq n \leq 1\,000$ 및 $0 \leq k \leq 10^9$가 성립한다.

다음으로 $n$개의 줄이 주어지며, 그중 $i$번째 줄은 앱이 보여 주는 $i$번째 동영상을 설명한다. $i$번째 줄에는 두 정수 $L_i, D_i$가 주어지며, 각각 $i$번째 동영상의 밀리초 단위 길이와 그 동영상을 끝까지 시청할 때 얻는 도파민의 양을 나타낸다. 항상 $0 \leq L_i \leq 100\,000$ 및 $0 \leq D_i \leq 10^9$가 성립한다.

마지막으로 Jarmína가 가진 총시간을 밀리초 단위로 나타내는 정수 $T$가 한 줄에 주어진다. 항상 $0 \leq T \leq 10^9$가 성립한다. 모든 동영상의 밀리초 단위 총길이를 $S$라고 하자. 항상 $0 \leq S \leq 100\,000$가 성립한다. 동영상은 Jarmína의 휴대전화에 표시되는 순서대로 주어진다.

Jarmína가 $T$밀리초 동안 얻을 수 있는 도파민의 최댓값을 출력한다.