Dudu는 배고픕니다. Dudu는 멋진 태국식 레스토랑에 앉았습니다. 놀랍게도 그는 모든 직원이 박사 학위를 갖고 있는 멋진 PhD 레스토랑에 있다는 것을 알게 되었습니다.
게다가, 각 직원들은 Dudu가 음식을 기다리는 동안 도전해볼 수 있는, 그들 각각의 전공 분야와 관련된 챌린지를 준비했습니다. i번 직원이 준비한 챌린지는 시도하려면 돈을 Ai만큼 지불해야 하며, 챌린지에 성공하면 Bi만큼 돈을 받습니다.
각 챌린지는 최대 1번 완료할 수 있으며 어떤 순서로든 시도할 수 있습니다. Dudu는 아주 똑똑해서 모든 챌린지를 성공할 수 있지만, i번 챌린지에 도전하기 전에 돈을 Ai만큼 지불할 수 있어야 합니다. Dudu가 돈을 M만큼 갖고 시작했을 때, 그가 얻을 수 있는 돈의 최댓값을 구하세요.
--------
[입력]
입력의 1번째 줄에는 2개의 정수 N, M이 주어집니다. N, M은 각각 챌린지의 수, Dudu가 처음에 갖고 있는 돈을 의미합니다.
다음 줄에는 N개의 수 A1, A2, ..., AN이 주어집니다. 이는 각 챌린지에 도전하기 위해 지불해야 하는 비용입니다.
마지막 줄에는 N개의 수 B1, B2, ..., BN이 주어집니다. 이는 각 챌린지를 완료했을 때의 보상입니다.
1 ≤ N ≤ 1000
0 ≤ M, Ai, Bi ≤ 106
--------
[출력]
Dudu가 벌 수 있는 돈의 최댓값을 출력합니다.
--------
[힌트]
Dudu는 처음에 돈을 100만큼 갖고 있습니다. Dudu는 다음과 같이 진행해 가장 많은 돈을 벌 수 있습니다:
80만큼 지불한 후 90을 돌려 받습니다. 이제 Dudu는 돈을 110만큼 갖고 있습니다.
50만큼 지불한 후 70을 돌려 받습니다. 이제 Dudu는 돈을 130만큼 갖고 있습니다.
110만큼 지불한 후 150을 돌려 받습니다. 이제 Dudu는 돈을 170만큼 갖고 있습니다.
moner_ari 1년 전
[문제]
"There is probably a place where all waiters have a PhD in, I don't know, some stuff." - Dudu, 2014
참고: 이 문제는 입력 제한이 더 작은 것을 제외하면 PhD 레스토랑 (Large)와 같은 문제입니다.
Dudu는 배고픕니다. Dudu는 멋진 태국식 레스토랑에 앉았습니다. 놀랍게도 그는 모든 직원이 박사 학위를 갖고 있는 멋진 PhD 레스토랑에 있다는 것을 알게 되었습니다.
게다가, 각 직원들은 Dudu가 음식을 기다리는 동안 도전해볼 수 있는, 그들 각각의 전공 분야와 관련된 챌린지를 준비했습니다. i번 직원이 준비한 챌린지는 시도하려면 돈을 Ai만큼 지불해야 하며, 챌린지에 성공하면 Bi만큼 돈을 받습니다.
각 챌린지는 최대 1번 완료할 수 있으며 어떤 순서로든 시도할 수 있습니다. Dudu는 아주 똑똑해서 모든 챌린지를 성공할 수 있지만, i번 챌린지에 도전하기 전에 돈을 Ai만큼 지불할 수 있어야 합니다. Dudu가 돈을 M만큼 갖고 시작했을 때, 그가 얻을 수 있는 돈의 최댓값을 구하세요.
--------
[입력]
입력의 1번째 줄에는 2개의 정수 N, M이 주어집니다. N, M은 각각 챌린지의 수, Dudu가 처음에 갖고 있는 돈을 의미합니다.
다음 줄에는 N개의 수 A1, A2, ..., AN이 주어집니다. 이는 각 챌린지에 도전하기 위해 지불해야 하는 비용입니다.
마지막 줄에는 N개의 수 B1, B2, ..., BN이 주어집니다. 이는 각 챌린지를 완료했을 때의 보상입니다.
--------
[출력]
Dudu가 벌 수 있는 돈의 최댓값을 출력합니다.
--------
[힌트]
Dudu는 처음에 돈을 100만큼 갖고 있습니다. Dudu는 다음과 같이 진행해 가장 많은 돈을 벌 수 있습니다: