**
**
给解决方案
看不清
能复制文字吗
Smmh去S市参加学术研讨会，会议结束后Smmh决定要给他的k个门徒一人带一份伴手礼回来。
Smmh来到了当地最大的集市上，从集市入口到出口一共按顺序摆了n个摊位。咱们把n个摊位看成一条坐标轴，第i个摊位的位置坐标在xi上，而集市的出口的坐标在xend上。
带着伴手礼行走是需要消耗体力的，如果Smmh身上有a份伴手礼，没走一个格就要消耗a * a的体力，走d格则消耗d * a * a的体力。
每个摊位的伴手礼的价格为ci，库存为fi。Smmh可以沿途在任何一个摊位购买不超过当前摊位库存量的伴手礼。
Smmh作为书生，体力实在有限，钱财也实在有限，因此Smmh既想省钱又想省力。你能不能帮助Smmh计算出，在购买满k份伴手礼到达出口的前提下，让体力消耗+钱财消耗的和尽量小，这个最小值为多少？
输入描述
第一行三个整数k,xend,n。
接下来n行，每行三个整数xi,fi,ci。
输出描述
输出一行一个整数，表示最小的体力消耗+钱财消耗之和。
样例1
输入复制
2 5 3 3 1 2 4 1 2 1 1 1
输出
9
提示
样例解释
在位置3和4的摊位各购买一个伴手礼，总钱财消耗为4，总体力消耗为1+2*2=5。
数据范围
对于50%的数据1<=k<=500,1<=n<=100,1<=xi<=xend<=100,1<=ci<=10^4,1<=fi<=500。
对于100%的数据1<=k<=10^4,1<=n<=500,1<=xi<=xend<=500,1<=ci<=10^6,1<=fi<=10000。
@陈俊哲 我老康康
这是哪里的题目？？
神秘网站上的
我一个同学发给我的
看代码和思路给解决方案
伪代码就行
有人吗？
有人吗？
有人吗？
有人吗？
有人吗？
有人吗？
有人吗？
有人吗？
有人吗？
有人吗？
有人吗？
有人吗？
有人吗？
有人吗？
有人吗？
首先，我们需要定义状态。我们可以定义一个二维数组dp[i][j] ，其中i 表示当前所在的摊位位置（从集市入口到出口的坐标），j 表示已经购买的伴手礼数量（从0到k）。dp[i][j] 的值表示在位置i 购买了j 份伴手礼后，体力消耗和钱财消耗之和的最小值。 如果没有达到当前位置，即i < n，则从上一个位置i-1转移过来，并考虑是否在当前位置购买伴手礼。如果已经购买了足够的伴手礼（即j >= k），则不再继续购买，直接走到出口。
在当前位置购买伴手礼时，我们需要考虑所有可能的购买数量（从0到min(j, f[i])），并选择其中消耗最小的那个。（可以去试试，窝不确定）
额。。。。。。
布泰冥百
就是说由于Smmh的体力消耗和钱财消耗都与伴手礼的购买数量和行走的格子数有关，我们可以考虑将问题分解为子问题，并使用一个数组或哈希表来存储子问题的解，用动态规划
@陈俊哲 解决方案呢？
hai mei jie jue ne
抱一丝， 还没学动规和哈希表，（窝是蒟蒻）
额。。。