재의 마녀의 여행

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

일레이나가 집으로 돌아가는 경로에는 $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$

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

• $1 \leq N \leq 101\,700$.
• $1 \leq C \leq 10^9$.
• $1 \leq A_i \leq 10^9$ ($1 \leq i \leq N$).
• $1 \leq B_i \leq 10^9$ ($1 \leq i \leq N$).
• 입력으로 주어지는 모든 값은 정수이다.