Монеты и гнезда

면접 대비

시간 제한2초메모리 제한1024 MB

요약

각 둥지 i에는 a_i개의 동전이 있고 총합이 b_i가 되면 떨어지며, m개의 동전을 던져 얻을 수 있는 동전의 최대 개수를 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

Петя долго-долго сидел у окна и наблюдал, как $n$ ворон, каждая в свое гнездо, приносят монеты. Петя заметил, что $i$ -ая ворона принесла в свое гнездо $a\_i$ монет. Опытным глазом Петя подметил, что если в $i$ -ом гнезде окажется $b\_i$ монет, то гнездо со всем своим содержимым упадет на землю, и все монеты достанутся Пете.

У Пети есть $m$ монет. Петя очень метко кидает монеты в гнезда. Помогите Пете узнать, какое максимальное число монет он может получить.

입력

В первой строке входного файла находятся два целых числа $n$ и $m$ ( $1 \le n \le 1000$ , $0 \le m \le 1000$ ) --- число ворон и монет у Пети соответственно. Во второй строке находятся $n$ чисел $a\_i$ ( $0 \le a\_i \le 1000$ ). В третьей строке находятся $n$ чисел $b\_i$ ( $a\_i < b\_i \le 1000$ ).

출력

В выходной файл выведите одно число --- максимальное число монет, которые Петя может получить.

예제2

예제 1
입력
```
2 3
1 2
4 6
```
예상 출력
```
6
```
예제 2
입력
```
3 3
1 2 3
4 8 16
```
예상 출력
```
4
```