No submission language available for this problem.

Background

Special for beginners, ^_^

Description

关小山要购买修仙用品时，总是用最少数量的灵石来进行交易，即他用来支付的灵石数量和收到找零的灵石数量之和是最少的。

他想购买 T (1≤T≤10000) 价值灵石的用品，而灵石系统有 N (1≤N≤100) 种不同的灵石，单位价值分别为 v₁, v₂, ... v_N (1≤v_i≤120)。关小山有 c_i 个单位价值为 v_i 的灵石 (0≤c_i≤10000)。

修仙用品店的店主拥有无限量的灵石，并且总是以最有效的方式进行交易（关小山必须确保通过其付款方式可以正确交易）。

Format

Input

第一行有两个整数 N 和 T。

第二行有 N 个整数 v_i

第三行有 N 个整数 c_i

Output

一行输出支付和找零的最小灵石数量，若不可能支付和找零，则输出 -1 。

Samples

3 70
5 25 50
5 2 2

3

Explain

一块 50 单位价值和一块 25 单位价值的灵石支付 75 单位价值，收取 5 单位价值的零头灵石，共三块灵石用于交易。

Limitation

1s, 1024KiB for each test case.