题目描述

有 N 棵小草，编号 0 至 N-1 。奶牛Bessie不喜欢小草，所以 Bessie 要用剪刀剪草，目标是使得这 N 棵小草的高度总和不超过 H 。在第 0 时刻，第 i 棵小草的高度是 h[i] ，接下来的每个整数时刻，会依次发生如下三个步骤：

1. 每棵小草都长高了，第 i 棵小草长高的高度是 grow[i]。

2. Bessie选择其中一棵小草并把它剪平，这棵小草高度变为 0 。注意：这棵小草并没有死掉，它下一秒还会生长的。

3. Bessie计算一下这N棵小草的高度总和，如果不超过H，则完成任务，一切结束，否则轮到下一时刻。

你的任务是计算：最早是第几时刻，奶牛 Bessie 能完成它的任务？如果第 0 时刻就可以完成就输出 0 ，如果永远不可能完成，输出 -1 ，否则输出一个最早的完成时刻。

输入格式

第一行，两个整数 N 和 H ( 1 ≤ N ≤ 50，0 ≤ H ≤ 1000000 )。

第二行，N 个整数，表示 h[i] ( 0 ≤ h[i] ≤ 100000 )。

第三行，N 个整数，表示 grow[i] ( 1 ≤ grow[i] ≤ 100000 )。

对于 20% 的数据，1 ≤ N ≤ 7 。

输出格式

一个整数，最早完成时刻或 -1 。

样例

3 16
5 8 58
2 1 1

1

2 58
5 8
2 1

0

2 0
5 8
2 1

-1

7  33
5  1  6  5  8  4  7
2  1  1  1  4  3  2

5

样例解释

样例 1 ：到了第1时刻，三棵小草的高度依次是 7,9,59 。如果奶牛 Bessie 把高度是 59 的小草剪掉，那么三棵小草高度是 7+9+0=16 ，任务完成。

样例 4 ：第 1 秒剪第 2 棵小草，第 2 秒剪第 0 棵小草，第 3 秒剪 6 棵小草，第 4 秒剪第 5 棵小草，第 5 秒剪第 4 棵小草。