작은 박사 식당

"아마 어딘가에는 웨이터 전원이 무언가의 박사 학위를 받은 식당이 있을 것이다." 두두, 2014년

두두는 배가 고파서 태국 음식점에 들어갔다. 자리에 앉고 나서야 알았는데, 그곳은 직원 모두가 무언가의 박사 학위를 받은 박사 식당이었다.

직원은 각자 자기 전공과 관련된 과제를 하나씩 준비해 두었고, 두두는 음식을 기다리는 동안 그 과제에 도전한다. $i$번 직원의 과제는 도전하려면 $A_i$를 내야 하고, 성공하면 $B_i$를 받는다.

과제는 각각 최대 한 번만 풀 수 있고, 도전하는 순서는 마음대로 정할 수 있다. 두두는 아주 똑똑해서 어떤 과제든 반드시 성공하지만, $i$번 과제에 도전하기 전에 $A_i$를 낼 수 있어야 한다. 두두가 처음 가진 돈이 $M$일 때, 두두가 최종적으로 얻을 수 있는 금액의 최댓값을 구하라.

첫 줄에 과제의 개수 $N$과 두두가 처음 가진 돈 $M$이 정수로 주어진다.

둘째 줄에 $N$개의 정수 $A_1, A_2, \dots, A_N$이 주어진다. $A_i$는 $i$번 과제에 도전하는 비용이다.

셋째 줄에 $N$개의 정수 $B_1, B_2, \dots, B_N$이 주어진다. $B_i$는 $i$번 과제를 성공했을 때 받는 금액이다.

• $1 \le N \le 1000$
• $0 \le M, A_i, B_i \le 10^6$

두두가 얻을 수 있는 금액의 최댓값을 정수 하나로 출력한다.

첫 번째 예제에서 두두는 100으로 시작해 다음 순서로 진행할 수 있다.

• 80을 내고 90을 받는다. 이제 110이 있다.
• 50을 내고 70을 받는다. 이제 130이 있다.
• 110을 내고 150을 받는다. 이제 170이 있다.