鹅国使用 $n$ 种鹅币作为其国家货币。第 $i$ 种鹅币的面值为 $c_i$ 鹅元，重量为 $w_i$。对于所有 $i$（$1 \le i \le n - 1$），$c_{i+1}$ 是 $c_i$ 的倍数，且 $c_i < c_{i+1}$。

你光顾了鹅市，购买了价值 $p$ 鹅元的商品。你想用恰好 $k$ 枚鹅币支付这一准确价格。每种硬币你都有无限多个，因此无需担心硬币不够用。

编写一个程序，求出总面值恰好为 $p$ 鹅元的 $k$ 枚硬币的最小和最大可能总重量。如果不存在这样的硬币组合，则输出 $-1$。

输入格式

第一行包含三个整数 $n$、$k$ 和 $p$（$1 \le n \le 60$，$1 \le k \le 10^3$，$1 \le p \le 10^{18}$）。$n$ 表示鹅币的种类数，$k$ 表示凑出恰好 $p$ 鹅元必须使用的硬币数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $c_i$（$1 \le c_i \le 10^{18}$）和 $w_i$（$1 \le w_i \le 10^{15}$），分别表示第 $i$ 种鹅币的面值和重量。

对于所有 $i$（$1 \le i \le n - 1$），$c_{i+1}$ 是 $c_i$ 的倍数，且 $c_i < c_{i+1}$。

输出格式

如果可以使用恰好 $k$ 枚硬币支付恰好 $p$ 鹅元，输出 $k$ 枚硬币的最小和最大可能总重量。否则，输出 $-1$。

样例

输入样例 1

3 9 20
1 2
2 5
6 10

输出样例 1

37 44

输入样例 2

2 5 10
1 1
3 3

输出样例 2

-1