README.md

[Gold IV] DDR 체력 관리 - 29756

문제 링크

성능 요약

메모리: 2568 KB, 시간: 0 ms

분류

다이나믹 프로그래밍, 배낭 문제

제출 일자

2024년 3월 19일 05:35:05

문제 설명

리듬게이머 코더빡은 최근 댄스 댄스 레볼루션(DDR)에 푹 빠져있다. 이 게임은 곡이 재생될 때 떨어지는 노트에 맞춰 발판을 밟는 게임으로, 많은 체력을 소모하기 때문에 체력 관리가 매우 중요하다.

곡은 N$N$개의 구간으로 이루어져 있고, 어떠한 구간 i$i$ (1≤i≤N)$(1 \le i \le N)$에 대해 코더빡은 해당 구간을 플레이할지, 포기할지 선택할 수 있다. 해당 구간을 플레이할 때 얻을 수 있는 점수는 si$s_i$점이며, 체력을 hi$h_i$만큼 소모한다. 구간을 포기할 때는, 점수를 얻지 못하고 체력도 소모하지 않는다.

곡이 시작할 때, 코더빡은 체력 100$100$을 가지고 시작한다. 매 구간에 진입하기 전에 체력을 K$K$만큼 회복한다. 이 체력 회복은 구간을 플레이하거나 포기하는 것과는 무관하게 일어남에 유의하라. 회복 후 코더빡의 체력이 100$100$을 초과하는 경우 체력이 100$100$이 되며, 구간을 플레이했을 때 체력이 0$0$ 미만으로 하락하는 경우 코더빡은 해당 구간을 포기해야만 한다.

하루 종일 DDR을 밟아 기진맥진인 코더빡은 더 이상 체력 관리를 위한 판단을 내릴 수 없다. 코더빡이 성과를 뽑아낼 수 있도록 그가 얻을 수 있는 최대 점수를 알려주는 프로그램을 작성하시오.

지문에서 언급하지 않은 게임오버 등의 시스템은 이 문제에서 고려하지 않는다.

입력

첫 번째 줄에는 두 정수 N$N$과 K$K$가 공백으로 구분되어 주어진다. N$N$은 곡의 전체 구간의 수를 의미하며, K$K$는 회복하는 체력의 양이다. (1≤N≤1000;$(1 \leq N \leq 1\,000;$ 1≤K≤10)$1 \leq K \leq 10)$ 

두 번째 줄에는 정수 s1$s_1$, s2$s_2$, ⋯$\cdots$, sN$s_N$이 공백으로 구분되어 주어진다. (1≤si≤1000)$(1 \leq s_i \leq 1\,000)$ 

세 번째 줄에는 정수 h1$h_1$, h2$h_2$, ⋯$\cdots$, hN$h_N$이 공백으로 구분되어 주어진다. (1≤hi≤100)$(1 \leq h_i \leq 100)$ 

출력

코더빡이 얻을 수 있는 최대 점수를 출력한다.