24041번 - 성싶당 밀키트

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

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

밀키트에는 $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$)
• 입력으로 주어지는 모든 수는 정수이다.