| 描述 |
|---|
有一条新建立的购物街，为了吸引消费者消费，该街联合举办了一个活动。规则：在一号店消费就可以获得“大径村7日游”，从一个店到另一个店需要消费满一定额度在花钱坐车去别的店并且可去的店是限定的，设立一个等级差距M，在一开始你没有等级，你去那个店就会获得该店的等级，如果你到等级低的店，那么你的等级就会变成等级低的店的等级，如果你的等级和店等级差超过M就不能进行交易。为该街所有店进行编号，从1号开始进行编号，并且这些店是有等级的。
ZSW是一个独特的消费者，他是土豪有的是钱，不在意消费多少钱，他想自己在游戏规则上玩，他想要知道在满足店内的消费额度后在所有的到1号的路线中，最多花多少钱（有钱就是任性）。 |
| 输入 |
| 输入第一行是3个整数M，N, D（1 <= N <= 100），依次表示等级差距限制和商店的总数、边的数量。接下来按照编号从小到大依次给出了N个店的信息。每个店有2个整数，分别表示为要在该店的等级Degree、该店消费的金额Money，接下来D行为图中边的数据，A，B，V分别表示为起点，终点，坐车价格。 |
| 输出 |
输出所有路线中最大的花费。 |
| 样例输入 |
1 4 4 3 10000 2 1000 2 3000 2 50 4 2 200 4 3 200 2 1 8000 |
| 样例输出 |
19250 |
| HINT |
所有路线均满足等级条件都可以存在 4->2->1 要花 50+200+1000+8000+10000=19250 4->3->1 要花 50+200+3000+5000+10000=18250 2->1 要花 1000+8000+10000=19000 3->1 要花 3000+5000+10000=18000 1 要花 10000 所以输出19250 |
| 来源 |
| XUJC OJ |