Description

badgers是可爱的动物，Manao想拥有一些。

宠物店提供N个badgers，编号为1..N，Manao都很喜欢，所以他想拥有得越多越好。

初始，每个badger每天需要固定量的食物。但是，如果它看见别的badger也在吃东西，它会觉得饥饿而吃更多的东西。

一个badger每多一个同食者需要增加一个固定量的食物。

hungeri表示第i个badger单独进食所需要的食物。

greedi表示第i个badger在每多一个同食者的情况下增加的食物量。

Manao每天最多可以供应totalFood量的食物，那么他最多可以养多少只badgers。

Format

Input

第一行两个整数N和totalFood。

第二行N个整数，第i个为Hungeri。

第三行N个整数，第i个为greedi。

Output

一个整数，表示Manao最多可以养多少只badgers。

Samples

3 7
1 2 3
2 2 1

2

4 19
5 2 1 5
0 2 4 1

3

1<=N<=50，

1<=hunger<=1000，

0<=greed<=1000，

1<=totalFood<=1000000