경곽이는 여름 축제를 구경하러 갔다. 축제는 저녁에 재미있는 게임을 할 수 있는 야시장형태로 N개의 가게가 영업을 하고 있다. 각각의 가게에는 1부터 n까지의 번호가 순서대로 붙어 있으며, 각 가게에서 놀 때 얻을 수 있는 즐거움과 노는데 걸리는 시간이 정수로 주어진다. 가게 i에서 놀 때 얻을 수 있는 즐거움은 Ai, 노는데 걸리는 시간은 Bi이다. 또 축제의 이벤트로 불꽃놀이를 한다. 시각 S에 가장 큰 불꽃이 터진다. 경곽이는 가장 큰 불꽃을 반드시 보고 싶어한다. 즉, 시각 S에는 가게에서 놀고 있으면 안된다. (불꽃놀이를 볼 수 없기 때문에 ^^) 경곽이는 가게에서 노는 것과 불꽃놀이를 모두 즐기기 위해 축제장소에 도착하는 시각을 0으로부터 축제가 끝나는 시각 T까지의 계획을 세우기로 했다. 경곽이는 가게들 중 k개(1<=k<=n)개의 가게를 골라 각각에 대해서 방문할 시각을 정했다. 같은 가게를 2번 들르지는 않는다. 고른 가게의 번호를 작은 순으로 y1, y2, .. ,yk라고 하고, 가게 yi를 방문할 때의 시각을 Xyi라고하면, 경곽이는 가게 yi에서 시각 Xyi로 부터 Xyi+Byi까지 가게에서 놀이를 한다. 경곽이는 가게의 번호가 작은 순으로 방문하며 동시에 2개의 가게를 방문할 수는 없다. 또 가게와 가게 사이의 이동시간은 무시한다. 시각 T를 넘으면 축제는 끝나므로 가게에서 놀 수 없다. 또 가게에서 놀고 있는 동안은 불꽃놀이를 볼 수 없다. 단, 시각 S가 어떤 가게에서 다 놀고 나오는 시각과 다른 가게에서 놀기 시작하는 시각일을 포함한 사이의 값일 때에는 놀이를 볼 수 있다. 즉, 예정은 다음 조건을 만족해야 한다. - y1 < y2 < ... < yk - Xy1, Xy2, ... , Xyk는 정수 - 0 <= Xy1 < Xy1 + By1 <= Xy2 < Xy2 + By2 <= ... <= Xyk < Xyk + Byk <= T - Xyi < S < Xyi + Byi가 되는 i는 존재하지 않는다. 주어진 가게의 즐겨움의 합 Ay1, Ay2, ... , Ayk의 합계를 M이라고 할 때, M이 최대가 되도록 하면서 불꽃놀이를 볼 수 있는 것이 경곽이의 목적이다. 이를 해결할 수 있는 프로그램을 작성하시오.

Night Market

문제 설명

입력

출력

예제

코드 제출

로그인

LOGIN