408877: GYM103371 E 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$$$.

3 9 20
1 2
2 5
6 10

37 44

2 5 10
1 1
3 3

-1