성싶당 밀키트

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

요약

각 재료의 부패 속도, 유통기한, 제거 가능 여부가 주어질 때, 중요하지 않은 재료를 최대 K개 제거한 뒤 총 세균 수가 G 이하가 되는 가장 늦은 날 x를 구한다.

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

문제

인스타 빵타쿠들의 꾸준한 사랑을 받는 베이커리 성싶당은 수현이가 그동안 쌓아온 노하우를 바탕으로 밀키트 사업에도 진출했다. 이제 성싶당의 맛을 집에서도 즐길 수 있다.

이 소식을 놓칠 리 없는 빵타쿠 한별이는 바로 성싶당에 달려가 밀키트를 사 왔다. 그러나 문제를 푸느라 바쁜 한별이는 깜빡 잊고 유통기한 안에 밀키트를 먹지 못했다. 눈물을 머금고 밀키트를 버리려고 포장을 뜯은 순간 한별이는 재료마다 유통기한이 다르다는 것을 발견했다. 밀키트의 유통기한은 모든 재료의 유통기한 중 가장 이른 것으로 결정되기 때문에 아직 유통기한이 지나지 않은 재료들이 남아 있었다.

밀키트에는 $N$ 개의 재료가 들어 있다. $i$ 번째 재료의 유통기한은 밀키트를 구매한 후 $L_i$ 일까지이고, 부패 속도는 $S_i$ 이다. 이 때 구매 후 $x$ 일에 $i$ 번째 재료에 있는 세균수는

$S_i \times \max\left( 1, x-L_i \right)$

마리이다. 단, $x$ 는 정수이다.

모든 재료의 세균수의 합이 $G$ 마리 이하일 경우 안심하고 먹을 수 있다. 밀키트를 너무 먹어보고 싶은 한별이는 중요하지 않은 재료를 최대 $K$ 개까지 빼서 세균수가 $G$ 마리 이하가 된다면 그냥 먹기로 했다.

한별이는 밀키트를 산 날부터 며칠 후까지 먹을 수 있을까?

입력

첫 번째 줄에 $N, G, K$ 가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번째 재료에 대한 정보인 부패 속도 $S_i$ , 유통기한 $L_i$ 와 중요한 재료인지를 나타내는 수 $O_i$ 가 주어진다. $O_i$ 는 $0$ 또는 $1$ 이며, $O_i=1$ 은 재료가 중요하지 않아서 뺄 수 있다는 의미이다.

출력

중요하지 않은 재료를 최대 $K$ 개까지 뺐을 때, 밀키트를 구매 후 며칠 후까지 먹을 수 있는지 출력한다.

제한

$1 \le N \le 200\,000$
$1 \le G \le 10^9$
$0 \le K < N$
$1 \le S_i \le 10^9$
$1 \le L_i \le 10^9$
$O_i \in \left\{0,1\right\}$
모든 재료의 $S_i$ 의 합은 $G$ 를 넘지 않는다. ( $\sum_{1 \le i \le n} S_i \le G$ )
입력으로 주어지는 모든 수는 정수이다.

예제3

예제 1
입력
```
4 36 0
2 14 1
3 8 1
5 12 1
7 10 0
```
예상 출력
```
12
```
예제 2
입력
```
4 36 1
2 14 1
3 8 1
5 12 1
7 10 0
```
예상 출력
```
13
```
예제 3
입력
```
4 36 2
2 14 1
3 8 1
5 12 1
7 10 0
```
예상 출력
```
14
```