열차 승차권 주문과 최대 수익

어떤 급행 열차가 A 역에서 출발하여 B 역까지 운행하며, 도중의 여러 역에 정차한다. 역에는 순서대로 번호가 매겨져 있고, A 역의 번호는 $0$, B 역의 번호는 $m$이다. 열차의 정원은 $n$명이며, 경로의 어느 구간에서도 열차에 타고 있는 승객 수의 합은 $n$명을 넘을 수 없다.

승차권의 가격은 출발역과 도착역 사이에 지나는 정차역의 수(도착역 포함)와 같다. 즉, 출발역 $S$에서 도착역 $T$까지의 승차권 가격은 $T - S$이다.

열차가 A 역을 출발하기 전에, 도중의 각 역으로부터 예약 주문을 받는다. 하나의 주문은 (출발역 $S$, 도착역 $T$, 승객 수 $P$)로 이루어지며, 회사는 각 주문을 통째로 받아들이거나 통째로 거절해야 한다. 정원 제한 때문에 모든 주문을 받을 수 없더라도, 한 주문의 일부 승객만 태우는 것은 허용되지 않는다.

어떤 주문을 받아들이면 그 $P$명의 승객은 $S$에서 $T$까지 이동하므로 그 사이의 모든 구간을 점유한다. 받아들인 한 주문에서 얻는 수익은 (승객 수) $\times$ (승차권 가격) $= P \times (T - S)$이며, 총수익은 받아들인 모든 주문의 수익의 합이다.

주어진 주문 목록에 대해, 회사가 얻을 수 있는 가장 큰 총수익을 구하는 프로그램을 작성하라.

입력은 여러 개의 블록으로 이루어진다. 각 블록의 첫 줄에는 세 정수 $n$, $m$, $k$가 주어진다. $n$은 열차의 정원, $m$은 B 역의 번호, $k$는 주문의 수이다. 이어지는 $k$개의 줄에는 각각 하나의 주문이 세 정수 $S$, $T$, $P$로 주어진다. $S$는 출발역, $T$는 도착역, $P$는 승객 수이다.

한 블록의 주문 수는 최대 $22$개이고, B 역의 번호 $m$은 최대 $7$이다. 첫 줄의 세 정수가 모두 $0$인 블록은 입력의 끝을 나타내며, 이 블록은 처리하지 않는다.

입력의 끝을 나타내는 블록을 제외한 각 블록에 대해, 얻을 수 있는 가장 큰 총수익을 한 줄에 하나씩 출력한다.