32618번 - 작전

문제

전쟁이 일어났다. 전쟁터는 1ドル$차원 배열로 표현된다. $i$번째 칸을 점령하기 위해서는 $i$와 인접한 칸 중 하나를 먼저 점령해야 한다. 또한 현재 가지고 있는 에너지가 $e_i$ 이상일 때에만 점령 가능하며, 점령했을 때 에너지가 $k_i$만큼 증가한다. $i$번째 칸을 점령한다고 $e_i$만큼 에너지가 감소하는 것은 아니다. 시작할 때 갖고 있는 에너지양은 $P$이며, 따라서 처음에 $e_i \le P$인 칸 중 하나를 자유롭게 선택하여 점령할 수 있다. 처음 선택하는 칸에 따라 점령할 수 있는 칸의 개수가 달라질 것이다. 최대한 많은 칸을 점령했을 때 점령한 칸의 개수를 출력하라.

입력

첫 번째 줄에 배열의 크기 $n,ドル 처음 갖고 있는 에너지양 $P$가 공백으로 구분되어 주어진다. (1ドル \le n \le 500,000円$; 0ドル \le P \le 10^9$)

두 번째 줄에 배열의 각 칸을 점령하는 데 필요한 에너지 $e_1, e_2, \dots ,e_n$이 공백을 사이에 두고 주어진다. (0ドル \le e_i \le 10^9$)

세 번째 줄에 배열의 각 칸을 점령했을 때 얻는 에너지 $k_1, k_2, \dots ,k_n$이 공백을 사이에 두고 주어진다. (0ドル \le k_i \le 10^9$)

출력

최대한 많은 칸을 점령했을 때 점령한 칸의 개수를 출력한다.

제한

힌트