背景

在华师一的敏行路上，新建了若干漂亮的路灯，这给同学们晚上的出行带来很大的方便。但是，问题随之出现了。

一天晚上，OI组的FHH 同学正往校门外走，忽然眼前一片漆黑，于是直接把眼镜都摔掉了，再也找不到。后来FHH 同学从学校管理处了解到昨晚路灯突然熄灭是因为电路不堪重负，导致空气开关跳闸。

描述

善于思考的FHH 同学考虑将路灯进行改建，以避免再次出现类似的问题。FHH同学仔细了解每盏路灯的耗电量a[i]与照明度z[i]，已知共有N 盏电灯，并且每盏电灯都可能有不同的耗电量与照明度，现在的问题是要把这N盏电灯分为M 组，新分出的每组灯的耗电量（即是该组所有打开电灯的耗电量之和）不能超过该组的电灯数目的T倍，在满足这样的前提下使得照明度尽可能的大，最后算出M 组的最大照明度的和。由于每组耗电量的限制，该组中的某些电灯可能不被使用，但是仍然应该算作该组灯的数目。特别注意的是电灯按顺序给出，只能把相邻的几盏灯分在一组。

由于计算较为复杂，FHH 同学经过反复的计算仍然不能确定结果，现在就请你为他编写一个程序来解决这个问题。

样例1

样例输入1

5 2 2
1 1
2 2
3 3
4 4
5 5

样例输出1

10

限制

1s

提示

对于70％的数据，保证有2<=N<=80，1<=M<=35，1<=T，a[i]，z[i]<=35；
对于全部的数据，保证有2<=N<=160，1<=M<=50，1<=T，a[i]，z[i]<=50。

来源

by hsyoi