택배

직선 도로 위에 왼쪽부터 오른쪽으로 $1$번, $2$번, $\dots$, $N$번이 차례로 매겨진 마을 $N$개가 놓여 있다. 물건을 배송하는 트럭이 한 대 있고, 트럭의 본부는 $1$번 마을 왼쪽에 있다. 트럭은 본부에서 출발해 $1$번 마을부터 $N$번 마을까지 오른쪽으로만 이동하며 각 마을의 물건을 배송한다.

각 마을은 배송할 물건을 박스에 담아 보내고, 본부는 배송마다 보내는 마을 번호, 받는 마을 번호, 박스 개수를 알고 있다. 모든 박스의 크기는 같으며, 트럭에는 한 번에 최대 $C$개의 박스만 실을 수 있다. 이 값을 트럭의 용량이라고 한다. 트럭 한 대로 다음 규칙을 모두 지키면서 최대한 많은 박스를 배송하려고 한다.

• 규칙 1: 트럭에 실은 박스는 그 박스의 받는 마을에서만 내린다.
• 규칙 2: 트럭은 이미 지나온 마을로 되돌아가지 않는다.
• 규칙 3: 한 배송의 박스 중 일부만 실어 배송해도 된다.

받는 마을 번호는 언제나 보내는 마을 번호보다 크다. 마을 수 $N$, 트럭 용량 $C$, 그리고 모든 배송 정보가 주어질 때, 트럭 한 대로 배송할 수 있는 박스의 최대 개수를 구하는 프로그램을 작성하라.

동작 방식을 예로 살펴보자. 트럭 용량이 $40$이고 배송 목록이 아래와 같다고 하자.

다음처럼 배송할 수 있다.

1. $1$번 마을에서 아래 박스들을 싣는다. $1 \to 4$ 배송은 $30$개 중 $10$개만 싣는다. 이제 트럭에는 $40$개가 실려 있다.

2. $2$번 마을에서 받는 마을이 $2$인 박스 $10$개를 내린다. 트럭에는 $30$개가 남는다. 이어서 아래 박스를 싣는다. 이제 $40$개가 실려 있다.

3. $3$번 마을에서 받는 마을이 $3$인 박스 $30$개를 내린다. 트럭에는 $10$개가 남는다. 이어서 아래 박스를 싣는다. 이제 $30$개가 실려 있다.

4. $4$번 마을에서 받는 마을이 $4$인 박스 $30$개를 내린다.

이렇게 하면 배송한 박스는 모두 $70$개이고, 이것이 배송할 수 있는 최대 개수이다.

첫째 줄에 마을 수 $N$과 트럭 용량 $C$가 공백을 사이에 두고 주어진다. ($2 \le N \le 2000$, $1 \le C \le 10000$)

둘째 줄에 배송 정보의 개수 $M$이 주어진다. ($1 \le M \le 10000$)

이어지는 $M$개의 줄에는 각 배송의 보내는 마을 번호, 받는 마을 번호, 박스 개수가 공백을 사이에 두고 주어진다. 박스 개수는 $1$ 이상 $10000$ 이하의 정수이고, 받는 마을 번호는 보내는 마을 번호보다 항상 크다.

트럭 한 대로 배송할 수 있는 박스의 최대 개수를 한 줄에 출력한다.