#P10509. Goose Coins
Goose Coins
Goose Coins
题目描述
有 种硬币,第 种面值为 ,重量为 ,每种数量无限。面值严格递增,并且对所有 , 都是 的整数倍。
需要恰好使用 枚硬币,凑出总面值 。求满足要求的硬币总重量的最小值和最大值。若不存在这样的组合,输出 。
输入格式
第一行三个整数 。
接下来 行,每行两个整数 ,表示面值和重量。
输出格式
有解时在一行输出最小总重量、最大总重量;无解时输出 -1。
样例 1 输入
3 9 20
1 2
2 5
6 10
样例 1 输出
37 44
样例 2 输入
2 5 10
1 1
3 3
样例 2 输出
-1
数据范围
,,,。
对所有 , 且 。