说明

你作为光之战士被召唤来了第一世界，在这里你需要做的事还是——帮忙跑腿。

在跑腿的过程中你发现，这里的人们将一个村的人分为三六九等，不同阶级之间有种种限制，如果你和村民B对话想要买他手里的道具，但是他发现你曾经和比他阶级低M个阶级的村民E交换过道具 他就会觉得你这人是低等人，并拒绝和你交换。

同样的，你也发现假设你在村长A那里买任务道具，同一个道具如果你直接买可能是5000块，但如果你将A想要的水晶球交给他，那A就会爽快地允许你用2000块交换你要买的那个道具，而水晶球可以从村民C那里购得，并且C也可以通过递交他想要的物品来降低水晶球的价格。

虽然你是光之战士大英雄，但是你的钱不多，所以你需要花尽可能少的钱来完成任务，请计算最少花多少钱就能买到任务道具？

输入格式

多组样例输入

每组样例第一行给出两个数M,N，整个交易过程中的阶级最高到最低的等级差不能高于M，村里的人数N

每行分别给出三个数a,b,c,当前村民的道具的原价a，村民本人所处地位b，该村民想要的道具数量c

之后c行每行给出两个数d,e，当前村民想要的道具的序号d，该村民得到这个道具后价格能给你便宜到e

输出格式

对每组样例都输出一个可以换得任务道具的最小花销。

样例

1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0

5250

提示

所有村民想要的物品都可以从其他村民那里购得，且每人都只持有一件道具。

每个人都可以通过“交给他他想要的东西”而得到友情价。

样例可以解释为：

阶级差距不能大于1，一共4个村民，

任务道具价格10000块，村长阶级为3，可以通过去拿2号村民的东西+8000块换取 或 拿3号村民的东西+5000块换取

2号村民的道具价格1000块，其本人阶级为2，可以通过拿4号村民的东西+200块换取

3号村民的道具价格3000块，其本人阶级为2，可以通过拿4号村民的东西+200块换取

4号村民的道具价格50块，其本人阶级为2，他没有想要的东西

那么最小花销：50先换4号村民的道具，再拿4号村民的道具+200块换3号村民的道具，最后拿3号村民的道具+5000块换任务道具，一共5250。