#205 home

Loading problem...

Preparing the statement, recent submissions, and submit form.

#205 home | DOJ

Authors: icly

Statement

재의 마녀 일레이나는 여러 나라를 여행하던 중 편지를 받고, 자신의 고향인 평화의 나라 로베타로 돌아가기로 했다.

일레이나가 집으로 돌아가는 경로에는 $N$ 개의 나라가 일렬로 놓여 있다. 일레이나는 경로를 따라 $1$ 번 나라, $2$ 번 나라, $\cdots$ , $N$ 번 나라를 차례로 지나간다.

현재 $X$ 개의 금화를 가지고 $i$ 번 나라에 도착했을 때, 일레이나는 다음 두 행동 중 하나를 선택한다.

나라를 방문하지 않고 지나간다. 이 경우 가지고 있는 금화의 수는 변하지 않는다.
나라를 방문하여 관광한다. $i$ 번 나라를 방문하려면 입국료로 $A_i$ 개의 금화를 내고, 추가로 $B_i$ 개의 금화를 담보로 맡겨야 한다. 따라서 $X \geq A_i+B_i$ 인 경우에만 방문할 수 있다.

일레이나는 관광할 때 입국료와 담보를 내고 남은 금화를 모두 사용한다. 출국할 때 맡겼던 담보 $B_i$ 개를 돌려받으므로, $i$ 번 나라를 방문한 뒤 일레이나가 가지고 있는 금화는 정확히 $B_i$ 개가 된다.

일레이나는 처음에 $C$ 개의 금화를 가지고 있다. 일레이나가 방문할 수 있는 나라의 개수의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ C$ $A_1\ A_2\ \cdots\ A_N$ $B_1\ B_2\ \cdots\ B_N$

첫째 줄에 일레이나가 방문할 수 있는 나라의 개수의 최댓값을 출력한다.

Sample 1

Input

10
1 4 1 1
8 3 6 2

Output

일레이나는 $2$ 번 나라를 방문한 뒤 금화 $8$ 개를 가지게 된다.

이후 $4$ 번 나라와 $5$ 번 나라를 차례로 방문하면 총 $3$ 개의 나라를 방문할 수 있다.

Sample 2

Input

4
5 1
1 4

Output

모든 나라에 입국하려면 $4$ 개보다 많은 금화가 필요하므로 어느 나라도 방문할 수 없다.