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

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

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

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

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

입력 형식

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

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

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

출력 형식

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

예제 입력 1

10 10
1 2 3 4 5 6 7 8 9 10
9 9 9 9 9 9 9 9 9 9

예제 출력 1

55

예제 입력 2

5 10
70 90 80 100 60
60 60 60 60 60

예제 출력 2

190