题目描述

在参加 ICPC World Finals 之前，你为了放松一下决定玩一个叫做 Quests 的电脑游戏。你已经玩过很多遍了，现在你想要达成完美通关——也是为了准备在 World Finals 中完美通关。

在游戏中，你需要完成一系列任务，完成每个任务都会获得一些经验点 (Xps)。在任何时刻，你目前的等级取决于获得的经验点。每当你获得 $v$ 点经验，你就会上升到一个新等级。形式上地，任何时刻你的等级是满足你至少有 $L\cdot v$ 点经验的最大的 $L$。

每个任务都有可获得的经验点数 $x$ 和一个目标难度等级 $d$。如果当你的等级至少为 $d$ 时你完成了这个任务，那么你会获得 $x$ 点经验。然而，如果当你的等级小于 $d$ 时你完成了这个任务，你将获得 $c\cdot x$ 点经验。常数 $c$ 是一个经验倍率，可以在你的等级小于推荐等级 $d$ 时完成任务的情况下获得额外的奖励。

你知道所有 $n$ 个任务与它们对应的 $x$ 和 $d$ 的值（并且你也知道 $v$ 和 $c$ 的值——毕竟你已经玩了很多次了）。你也足够高玩，知道在任何等级下完成任何目标难度的任务的方法。你想要在让你获得最大可能的经验点数的情况下完成所有任务。

例如样例输入中，最大可以获得的经验点数为 $43$，可以如下操作。首先完成第二个任务（你会获得 $4$ 经验点数，因为你现在等级为 $0$，你挑战了一个目标难度为 $2$ 的任务）。然后完成第一个任务（你会获得 $34$ 经验点数，因为你仍然在等级 $0$，挑战了一个目标难度为 $1$ 的任务）。现在你有 $34$ 经验点，处于等级 $3$。最后，完成第三个任务（你会获得 $9$ 经验点数，并且不会获得经验倍率，因为你已经在等级 $3$ 了）。

输入格式

第一行包含三个整数 $n,v,c$，其中 $n\ (1\le n\le 2\ 000)$ 是游戏中任务的个数，$v\ (1\le v\le 2\ 000)$ 是升到每一级所需的经验点数，$c\ (2\le c\le 2\ 000)$ 是在等级达到每个任务的目标等级前完成任务所能获得的经验倍率。

接下来 $n$ 行，每行包含两个整数 $x,d$，描述每个任务。其中 $x\ (1\le x\le 2\ 000)$ 是当你的等级大于或等于这个任务的目标难度等级 $d\ (1\le d\le 10^6)$ 时完成这个任务所能获得的经验点数。

输出格式

输出当你完成所有任务时所能获得的最大经验点数。

3 10 2
15 1
2 2
9 1

43