Preparing NOJ # Goose Coins

3000ms 1048576K

## Description:

The Goose Kingdom uses $n$ types of goose coins as their national currency. The $i$-th type of goose coin has a value of $c_i$ goose-dollars and a weight of $w_i$. For all $i\ (1 \le i \le n-1)$, $c_{i+1}$ is a multiple of $c_i$ and $c_i < c_{i+1}$.

You visited Goose Market and bought $p$ goose-dollars worth of goods. You want to pay the exact price using exactly $k$ goose coins. You have infinitely many coins of each type, so you don't have to worry about running out of coins.

Write a program to find the minimum and maximum possible total weights of $k$ coins with total value of $p$ goose-dollars. If there is no such set of coins, output $-1$.

## Input:

The first line contains three integers $n$, $k$, and $p\ (1\le n \le 60, 1\le k \le 10^3, 1\le p \le 10^{18})$. $n$ is the number of types of goose coins. $k$ is the number of coins you have to use to make exactly $p$ goose-dollars.

In the following $n$ lines, the $i$-th line contains two integers $c_i\ (1 \le c_i \le 10^{18})$ and $w_i\ (1\le w_i \le 10^{15})$, representing the value and the weight of the $i$-th type of goose coin.

For all $i\ (1 \le i \le n-1)$, $c_{i+1}$ is a multiple of $c_i$ and $c_i < c_{i+1}$.

## Output:

If it is possible to pay exactly $p$ goose-dollars using exactly $k$ goose coins, output the minimum and maximum possible total weights of the $k$ coins. Otherwise, output $-1$.

## Sample Input:

3 9 20
1 2
2 5
6 10


## Sample Output:

37 44


## Sample Input:

2 5 10
1 1
3 3


## Sample Output:

-1


Info Provider CodeForces Gym

Code GYM103371E

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/31/2021 14:45:07

Related

Nothing Yet