题目描述

食堂的张师傅，开车来到市场采购粮食。

市场是一条笔直的直线，从位置 0 开始 到位置 N 结束，每个整点上都开设了一个商店。

这些商店中，只有 M 个商店是粮食店，供应张师傅需要采购的粮食，这 M 个商店中第 i 个商店的位置为 xi​，粮食单价为 pi​ 元每公斤，有 ci​ 公斤的粮食供应给客人购买。

张师傅的车如果装了 T 公斤的粮食，每行驶一个单位的距离，就要消耗 T 元的油费，如果没有装粮食，油费忽略不计。

张师傅一共要采购 S 公斤的粮食，请问他从位置 0 开始，如果中途可以在任意的粮食店采购粮食，但不能回头，并一定要行驶到位置 N 处，那么他最少要花费多少元？

输入格式

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

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

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

输出格式

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

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

7