bzoj#P1716. [Usaco2006 Dec]The Fewest Coins 找零钱

[Usaco2006 Dec]The Fewest Coins 找零钱

题目描述

农夫 John 想到镇上买些补给。为了高效地完成任务,他想使硬币的转手次数最少。即使他交付的硬币数与找零得到的的硬币数最少。John 想要买 tt 样东西。有 nn 种货币参与流通,面值分别为 v1,v2vnv_1,v_2\dots v_n。John 有 cic_i 个面值为 viv_i 的硬币。我们假设店主有无限多的硬币,并总按最优方案找零。

输入格式

  • Line 11:两个整数 nntt
  • Line 22nn 个数,表示 v1,v2,vnv_1, v_2,\dots v_n
  • Line 33nn 个数,表示 c1,c2,cnc_1, c_2,\dots c_n

输出格式

  • Line 11:一个整数,表示最优方案的转手次数,如无解输出 -1
3 70
5 25 50
5 2 1
3

数据规模与约定

对于 100%100\% 的数据,1t1041\le t\le 10^41n1001\le n\le 1001vi1201\le v_i\le 1200ci1040\le c_i\le 10^4

题目来源

Gold