SHOW ME THE DUNGEON

올여름 출시된 RPG 게임 "SHOW ME THE DUNGEON"에서 주인공 시루는 몬스터에게 침략당한 마을을 구한다. 나라에는 0번부터 N번까지 번호가 붙은 N+1개의 마을이 있다. 0번 마을과 1번부터 N번까지의 마을을 오갈 수 있는 도로가 있고, 이 밖의 도로는 없다. 즉, 도로는 모두 N개이다.

게임이 시작하면 시루는 0번 마을에 있다. 0번 마을을 제외한 1번부터 N번 마을에는 몬스터가 한 마리씩 있다. 시루는 도로를 따라 마을을 방문하며, 한 마을에서 다른 마을로 가려면 반드시 0번 마을을 거쳐야 한다. 시루는 몇 개의 마을을 골라 적당한 순서로 방문해 몬스터와 싸울 것이다.

$i$번 마을의 몬스터는 공격력이 $A_i$이고, 그 마을에는 $P_i$명의 주민이 있다. 시루는 마을을 방문하면 몬스터와 싸운 뒤 주민을 해방시킨다. 시루의 초기 체력은 $K$이다. 마을 $i$를 방문하기 전에 마을 $t_1, t_2, \cdots, t_k$를 방문했다면, 마을 $i$에서 몬스터와 싸울 때 체력을 $A_{t_1} + A_{t_2} + \cdots + A_{t_k} + A_i$만큼 소모한다. 시루의 체력이 0보다 작아지면 주민을 해방시키지 못하고 게임이 끝난다.

모든 마을의 주민을 해방시키는 것은 불가능할 수 있다. 그래서 시루는 체력을 최대 $K$만큼만 소모하면서 최대한 많은 주민을 해방시키려고 한다. 시루가 해방시킬 수 있는 주민 수의 최댓값을 구하시오.

첫째 줄에 몬스터의 수 $N$과 시루의 초기 체력 $K$가 공백으로 구분되어 주어진다.

둘째 줄에 각 마을 몬스터의 공격력 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

셋째 줄에 각 마을의 주민 수 $P_1, P_2, \cdots, P_N$이 공백으로 구분되어 주어진다.

입력으로 주어지는 모든 값은 정수이다.

시루가 해방시킬 수 있는 주민 수의 최댓값을 출력한다. 주민을 한 명도 해방시킬 수 없다면 0을 출력한다.

• $1 \leq N \leq 20$
• $1 \leq K \leq 100\,000$
• $1 \leq A_i \leq 100\,000$
• $1 \leq P_i \leq 100\,000$