UVA301 Transportation

新修的从 A 城到 B 城的高速铁路将于近日开通。这条线路上沿途的车站从 A 城车站到 B 城车站依次编号为 $0,1,\cdots,m$。在开通之前，铁路公司从沿途的所有车站中收集到了 $t$ 条订单，第 $i$ 条订单的信息包括起点站编号，终点站编号和乘车人数。然而这条高速铁路上的列车最多只能承载 $n$ 人，因此你不得不拒绝一些订单。 你知道一条订单能带来的利润为起点站到终点站之间的车站数量（**包括终点站，但不包括起点站**）乘以乘车人数。你现在想知道如果按照最优策略接受订单，最多能够带来多少利润。

**本题单个测试点有多组数据。** 对于每组数据，第一行输入三个整数 $n,m,t$，分别表示列车的最大承载人数，**除 A 城车站之外**的车站数量和订单数量。 随后 $t$ 行，第 $i+1$ 行输入三个整数 $u,v,w$，分别表示第 $i$ 条订单的起点站编号，终点站编号和乘车人数。 当第一行输入的三个整数都是 $0$ 时，停止输入。

对于每组数据，输出一行一个整数，表示按照最优策略接受订单最多能够带来的利润。

对于所有数据，$m\leqslant 7$，$t\leqslant 22$。 Translated by Eason_AC