题目描述

安博士有N种重量不同的积木，第i种积木有Ai个，重量为Wi个单位。现在他要求小明用这些积木中的若干块堆成多个积木塔，对于每一座积木塔中上下直接相邻两个积木来说，下面的积木要比上面的积木重至少K个单位。安博士希望最终堆成的积木塔个数最多为M，那么最多能有多少个积木将参与到这些积木塔的堆建之中？

输入

第1行3个整数N,M,K。 接下来N行，每行2个整数Wi和Ai，数据保证所有Wi均不相同。

输出

输出一个整数，表示答案。