25791번 - Lecture Allocation 다국어

You are the coordinator for a competitive programming club. You need to hire some teachers to give lectures. There are a fixed number of lectures that need to be given this year. Additionally, there are a limited number of teachers that are willing to give lectures. Each teacher can teach up to three lectures, but not all the teachers need to teach a lecture, i.e., a teacher could teach 0, 1, 2, or 3 lectures. Each teacher charges a different amount depending on the number of lectures they give.

The money not spent will be used to fly the team to other contests, so you want to spend as little money as possible hiring enough teachers to give all the lectures.

Given the number of lectures to teach and how much each teacher charges for giving the lectures, determine the least amount of money necessary such that all the lectures will be taught.

The first input line contains two integers, L and T (1 ≤ L ≤ 5000, L/3 ≤ T ≤ L), representing (respectively) the number of lectures and the number of teachers. Each of the following T input lines contains three integers, the i th of which contains a_i1, a_i2, and a_i3 (0 < a_i1 < a_i2 < a_i3 ≤ 100,000), representing (respectively) how much the i th teacher charges to give 1, 2, and 3 lectures.

Print on a single line by itself a single positive integer: the least cost for paying the teachers to cover all L lectures. Assume that there are enough teachers to cover all the lectures.

For the first Sample Input, the first teacher can give two lectures and the third teacher can give two lectures, so the total cost is 10 + 17 = 27.

For the third Sample Input, the first teacher can give two lectures and the second teacher can give three lectures, so the total cost is 20 + 37 = 57.