In-Flight Meal Trip

There are N cities arranged from east to west and numbered 1 through N in that order. City 1 is the easternmost city, and city N is the westernmost city.

You are planning a trip that visits at most M of these cities. The trip must start at city 1 and end at city N, and both of those cities count toward the number of visited cities. Because you are sensitive to time-zone changes, you cannot move west and then return east. Therefore, every move in the trip must go to a city with a larger number.

Travel between cities is by airplane, but not every pair of cities has a flight. Each flight has a score for the in-flight meal it provides. Given the available flights, find the maximum possible total score of the meals eaten during the trip.

The first line contains the number of cities N, the maximum number of cities that may be visited M, and the number of available flights K.

• 1 <= N <= 300
• 2 <= M <= N
• 1 <= K <= 100,000

Each of the next K lines contains three integers a, b, and c describing one flight. This means there is a flight from city a to city b, and its meal score is c.

• 1 <= a, b <= N
• 1 <= c <= 10,000
• No input has a = b.

Flights whose destination city number is smaller than the departure city number may appear in the input, and multiple flights may be given for the same ordered pair of cities.

Print the maximum total meal score that can be obtained during the trip.