DDR 체력 관리

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

곡은 $N$개의 구간으로 이루어져 있다. 각 구간 $i$ $(1 \leq i \leq N)$에 대해 코더빡은 그 구간을 플레이하거나 포기할 수 있다. 구간을 플레이하면 $s_i$점을 얻고 체력을 $h_i$만큼 소모한다. 구간을 포기하면 점수를 얻지 못하고 체력도 소모하지 않는다.

곡이 시작될 때 코더빡의 체력은 $100$이다. 매 구간에 들어가기 전에 체력이 $K$만큼 회복된다. 이 회복은 구간을 플레이하거나 포기하는 것과 관계없이 항상 일어난다. 회복 후 체력이 $100$을 넘으면 체력은 $100$이 된다. 구간을 플레이했을 때 체력이 $0$ 미만으로 떨어지면 코더빡은 그 구간을 포기해야 한다.

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

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

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

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

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

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