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이 주어집니다. 이는 각 챌린지를 완료했을 때의 보상입니다.

  • 1 ≤ N ≤ 1000
  • 0 ≤ M, Ai, Bi ≤ 106

--------

[출력]

Dudu가 벌 수 있는 돈의 최댓값을 출력합니다.

--------

[힌트]

Dudu는 처음에 돈을 100만큼 갖고 있습니다. Dudu는 다음과 같이 진행해 가장 많은 돈을 벌 수 있습니다:

  • 80만큼 지불한 후 90을 돌려 받습니다. 이제 Dudu는 돈을 110만큼 갖고 있습니다.
  • 50만큼 지불한 후 70을 돌려 받습니다. 이제 Dudu는 돈을 130만큼 갖고 있습니다.
  • 110만큼 지불한 후 150을 돌려 받습니다. 이제 Dudu는 돈을 170만큼 갖고 있습니다.

댓글을 작성하려면 로그인해야 합니다.