题目描述

食堂的张师傅开车来到市场采购粮食。市场是一条笔直的直线，从位置0开始到位置N结束，每个整点上都开设了一个商店。这些商店中，只有M个商店是粮食店，供应张师傅需要采购的粮食。这M个商店中第i个商店的位置为xi，粮食单价为pi元每公斤，有ci公斤的粮食供应给客人购买。

张师傅的车如果装了T公斤的粮食，每行驶一个单位的距离，就要消耗T元的油费；如果没有装粮食，油费忽略不计。张师傅一共要采购S公斤的粮食，他从位置0开始，中途可以在任意的粮食店采购粮食，但不能回头，并且一定要行驶到位置N处。请问他最少要花费多少元？

输入格式

第1行读入整数S、N、M。

接下来M行，每行读入3个整数xi、ci、pi，含义如题所述。

请注意：本题在同一个位置，可能会有多家粮食店。

数据范围：

• 对于100%的数据，1≤S≤100，1≤N≤350，1≤M≤100。
• 对于100%的数据，0<x<N，1≤c≤100，1≤pi≤10^6。
• 数据保证所有粮食店的粮食供应量的总和能够满足张师傅的采购要求。

输出格式

输出一个整数，代表张师傅的最少花费。

样例输入

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

样例输出

7

提示

样例1解释： 张师傅要采购2公斤的粮食，整条街从位置0~5开设有商店，有3个位置上开设有粮食店。 在位置3的粮食店购买1公斤的粮食，运输到位置5，采购费用：2元，运输费用2元。 在位置4的粮食店购买1公斤的粮食，运输到位置5，采购费用：2元，运输费用1元。 共计花费=2+2+2+1=7元。