시간 제한메모리 제한제출정답맞은 사람정답 비율
3 초 (추가 시간 없음) 1024 MB90221522.059%

문제

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

예제 입력 1

3 9 20
1 2
2 5
6 10

예제 출력 1

37 44

예제 입력 2

2 5 10
1 1
3 3

예제 출력 2

-1

출처

University > KAIST > 2021 KAIST 11th ICPC Mock Competition E번