你是韩国顶级摇滚明星 Koosaga 的忠实粉丝。令人兴奋的是，Koosaga 宣布举办一场抽奖活动，为粉丝提供一次千载难逢的面对面交流机会。

Koosaga 出售 $n$ 种专辑。当你购买第 $i$ 种专辑时，需要花费 $a_i$ 韩元，并获得 $b_i$ 张抽奖券。你可以根据需要购买同一专辑的多份。

在抽奖当天，一个巨大的轮盘赌轮上包含写有参与者名字的格子，以此决定获胜者。轮盘上的每个格子被选中的概率相等。写有你名字的格子数量对应于你所积累的抽奖券数量。

Koosaga 将转动一次轮盘来选出获胜者。但如果最初运气不佳，仍有希望！通过支付 $r$ 韩元，你可以要求 Koosaga 再次转动轮盘。你可以根据需要支付任意次数的重转费用。

凭借内幕消息，你得知归属于其他参与者的格子总数为 $s$。重要的是，他们都不会选择重转。

你的挑战是找到一种最优策略，以最小的期望成本赢得比赛。

输入格式

第一行包含三个整数：$n$、$s$ 和 $r$ ($1 \le n \le 10^5$; $1 \le s \le 10^6$; $1 \le r \le 10^6$)。 接下来的 $n$ 行中，第 $i$ 行包含两个整数：$a_i$ 和 $b_i$ ($1 \le a_i \le 300$; $1 \le b_i \le 5000$)。

输出格式

输出一行，包含两个互质的正整数 $x$ 和 $y$。数值 $\frac{x}{y}$ 必须是获胜的最小期望成本。保证最小期望成本可以表示为这种格式。

样例

输入 1

3 11 3
1 3
2 7
5 13

输出 1

63 10