23174번 - Goose Coins 다국어

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$.

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}$.

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$.