You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

农夫 John 想到镇上买些补给。为了高效地完成任务，他想使硬币的转手次数最少。即使他交付的硬 币数与找零得到的的硬币数最少。

John 想要买价值为 $T(1 \le T \le 10,000)$ 的东西。有 $N(1 \le N \le 100)$ 种货币参与流通，面值分别为 $V_1,V_2,\dots,V_N(1 \le V_i \le 120)$。John 有 $C_i$ 个面值为 $V_i$ 的硬币（$0 \le C_i \le 10 ^ 4$）。

我们假设店主有无限多的硬币， 并总按最优方案找零。注意无解输出 -1。

输入格式

第一行两个整数 $N,T$。

第二行 $N$ 个整数 $V_1 \sim V_N$。

第三行 $N$ 个整数 $C_1 \sim C_N$。

输出格式

一个整数表示答案（无解输出 $-1$）。

3 70
5 25 50
5 2 1

3

提示

样例的最优方案：农夫 John 支付面值 $50$ 和 $25$ 的硬币各一枚，店主找回面值为 $5$ 的硬币一枚。