문제
민성이는 도시를 운영하는 게임을 즐겨한다.
게임은 자원을 C만큼 가지고 시작하며, 자원을 사용해서 도시에 생산 시설을 건설할 수 있다.
생산시설은 모두 N종류가 있으며, 이들은 각각 Ai일차 일때만 설치할 수 있다는 제약이 있다.
설치할 때는 Bi의 비용이 들고, 생산시설을 철거한다면 Ci의 자원을 돌려받을 수 있다.
설치된 생산시설은 설치된 날의 다음날부터 철거되기 전날까지 매일 Di의 자원을 생산한다.
게임의 온갖 컨텐츠를 섭렵해버린 민성이는 지금 모든 도전과제 클리어를 목표로 하고 있다.
민성이가 노리고 있는 도전과제 “두 개는 필요 없어”는 K일차까지 생산시설을 한 번에 2개 이상 가지지 않고 게임을 진행해야 클리어할 수 있다!
즉, 다른 생산시설을 설치하려면 기존의 생산시설을 철거해야 한다. 다행스럽게도 기존의 시설을 철거한 날 바로 다른 시설을 설치할 수 있다.
민성이는 K일이 모두 지나가면 가진 생산시설을 철거할 생각이고, 한 번에 하나의 생산시설만 가지고 최대한의 자원을 얻으려고 한다. (도전과제가 목표이므로 자원을 다른 곳에 사용하지는 않는다.)
알고리즘 전문가인 여러분들이 민성이를 도와주자!
입력
첫 번째 줄에 N(1 ≤ N ≤ 105), C(1 ≤ C ≤ 109), K(1 ≤ K ≤ 109)가 공백을 사이에 두고 주어진다.
두 번째 줄부터 N줄에 걸쳐 Ai, Bi, Ci, Di가 공백을 사이에 두고 주어진다. (1 ≤ Ai ≤ K, 1 ≤ Ci < Bu ≤ 109, 1 ≤ Di ≤ 109)
각 값의 의미는 문제 설명에 적힌 것과 동일하다.
출력
K+1일차에 가진 생산시설을 모두 철거한 민성이가 가질 수 있는 최대 자원을 한 줄에 출력한다.
예제
6 10 20
6 12 1 3
1 9 1 2
3 2 1 2
8 20 5 4
4 11 7 4
2 10 9 1
44
로그인해야 코드를 작성할 수 있어요.