#P10509. Goose Coins

    ID: 9626 传统题 2000ms 256MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>CF2300提高+/省选-完全背包同余的加减乘运算滚动数组

Goose Coins

Goose Coins

题目描述

有 nn 种硬币,第 ii 种面值为 cic_i,重量为 wiw_i,每种数量无限。面值严格递增,并且对所有 1≤i<n1\le i<n,ci+1c_{i+1} 都是 cic_i 的整数倍。

需要恰好使用 kk 枚硬币,凑出总面值 pp。求满足要求的硬币总重量的最小值和最大值。若不存在这样的组合,输出 −1-1。

输入格式

第一行三个整数 n,k,pn,k,p。

接下来 nn 行,每行两个整数 ci,wic_i,w_i,表示面值和重量。

输出格式

有解时在一行输出最小总重量、最大总重量;无解时输出 -1。

样例 1 输入

3 9 20
1 2
2 5
6 10

样例 1 输出

37 44

样例 2 输入

2 5 10
1 1
3 3

样例 2 输出

-1

数据范围

1≤n≤601\le n\le60,1≤k≤1031\le k\le10^3,1≤p,ci≤10181\le p,c_i\le10^{18},1≤wi≤10151\le w_i\le10^{15}。

对所有 1≤i<n1\le i<n,ci<ci+1c_i<c_{i+1} 且 ci∣ci+1c_i\mid c_{i+1}。