小D和他的魔法石

题号：NC214271
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小 $\text{D}$ 是一个喜欢研究算法的大魔法师。有一天，他在魔法森林里找到了 $\mathop n$ 棵魔法树，其中第 $\mathop i$ 棵魔法树可以生产无限块抗力为 $a_i$ ，魔力为 $b_i$ 的魔法石。同时，由于小 $\text{D}$ 法力强大，他有 $\mathop k$ 次机会，每次可以交换其中两棵魔法树能够产生的魔法石的魔力。
小 $\text{D}$ 可以吸收魔法石的能量。每吸收一块魔法石的能量，他的抗力就会减少对应魔法石的抗力，魔力就会增加对应魔法石的魔力。他的初始抗力为 $\mathop m$ ，魔力为 $\text 0$ 。一旦他的抗力小于 $\text 0$ ，他就没法施展魔法了。现在，小 $\text{D}$ 想知道，自己在抗力不小于 $\text 0$ 的前提下，最大的魔力是多少。
注意，小 $\text{D}$ 必须先使用完所有的交换机会，再吸收魔法石的能量。

输入描述:

输入共行。
第一行包含个正整数和个非负整数。
第二行包含个正整数，第个数表示。
第三行包含个正整数，第个数表示。

输出描述:

输出共一行，包含一个非负整数，表示最大的魔力。

示例1

输入

复制

2 5 0
1 2
1 3

输出

复制

说明

由于，所以没有交换机会。
吸收魔法树的块魔法石，吸收魔法树的块魔法石。
此时小的抗力，魔力。

示例2

输入

复制

2 5 1
1 2
1 3

输出

复制

说明

使用唯一的交换机会，交换魔法树，魔法树能够产生的魔法石的魔力。
吸收魔法树的块魔法石，吸收魔法树的块魔法石。
此时小的抗力，魔力。