lntanx 给农场供应尿素肥料。一天,一家农场下了订单,制作这批肥料需要 桶氨。仓库里已经没有氨了,因此 lntanx 决定购买氮气和氢气来合成氨。
每批合成消耗 桶氮气和 桶氢气,产出 桶氨。合成本身没有额外费用。只能合成整数批,可以生产超过所需数量的氨。
氮气有 家供应商,氢气有 家供应商。已知每家供应商的库存量和每桶价格。可以从任意供应商处购买不超过其库存量的整数桶,也可以从多家供应商处购买同一种原料。
求获得至少 桶氨所需的原料采购费用的最小值。
第一行包含三个用空格分隔的整数 、 和 ,分别表示氮气供应商的数量、氢气供应商的数量和所需的氨的数量。
接下来 行每行描述一家氮气供应商,随后 行每行描述一家氢气供应商。每家供应商的信息占一行,包含两个用空格分隔的整数 和 ,分别表示库存量和每桶价格。
在第一行输出最小费用。如果原料不足,无法生产至少 桶氨,则输出 -1。
建议使用有符号 64 位整数类型计算费用。
从第一家氮气供应商购买 单位、从第二家购买 单位,费用为 。从第一家氢气供应商购买 单位、从第二家购买 单位,费用为 。这些原料可以合成 桶氨。