Description

约翰进城买农产品时总是以最小数量的 硬币来交易，即他用来支付的硬币数量和收到找零的硬币数量之和是最小的。

他想购买$T$ $（$$1$$≤$$T$ $≤$$1$$0$$0$$0$$0$$）$美分的用品，而硬币系统有$N$ $（$$1$$≤$$N$ $≤$$1$$0$$0$$）$种不同的硬币，面值分别为$v$ $1$ , $v$ $2$ , …, $v$$N$ $（$$1$$≤$$v$$i$ $≤$$1$$2$$0$$）$。

约翰有$c$ $1$ 个面值为$v$ $1$ 的硬币，$c$ $2$ 个面值$v$ $2$ 的硬币, …, 个面值$v$$N$ $（$$0$$≤$$c$$i$ $≤$$1$$0$$0$$0$$0$$）$的硬币。

店主拥有无限量的硬币，并且总是以最有效的方式进行交易$（$约翰必须确保通过其付款方式可以正确交易$）$。

Format

Input

第$1$行有两个整数$N$ 和$T$ 。

第$2$行有$N$ 个整数$v$ $1$ , $v$ $2$ , …, $v$$N$ ，表示硬币的面值。

第$3$行有$N$ 个整数$c$ $1$ , $c$ $2$ , …, $c$$N$ ，表示硬币 的数量。

Output

单行输出支付和找零的最小硬币数，若不可能支付和找 零，则输出-$1$。

Samples

3 70
5 25 50
5 2 2

3

来源

POJ3260