你是编程竞赛俱乐部的协调员。你需要聘请一些老师来授课。今年有固定数量的课程需要讲授。此外，愿意授课的老师数量有限。每位老师最多可以讲授三门课程，但并非所有老师都必须授课，即一位老师可以讲授 0、1、2 或 3 门课程。每位老师根据他们讲授的课程数量收取不同的费用。

未花费的资金将用于资助团队参加其他比赛，因此你希望在聘请足够多老师讲授所有课程的前提下，花费尽可能少的钱。

题目描述

给定需要讲授的课程数量以及每位老师讲授不同数量课程的收费标准，确定讲授所有课程所需的最少金额。

输入格式

第一行包含两个整数 $L$ 和 $T$ ($1 \le L \le 5000$, $L/3 \le T \le L$)，分别代表课程数量和老师数量。接下来的 $T$ 行中，第 $i$ 行包含三个整数 $a_{i1}, a_{i2}, a_{i3}$ ($0 < a_{i1} < a_{i2} < a_{i3} \le 100,000$)，分别代表第 $i$ 位老师讲授 1、2 和 3 门课程的收费。

输出格式

输出一行，包含一个正整数：覆盖所有 $L$ 门课程所需的最小花费。假设有足够的老师来覆盖所有课程。

样例

样例输入 1

4 3
8 10 20
10 20 30
11 17 25

样例输出 1

27

样例输入 2

6 2
10 20 25
30 35 37

样例输出 2

62

样例输入 3

5 2
10 20 25
30 35 37

样例输出 3

57

说明

对于第一个样例输入，第一位老师可以讲授两门课程，第三位老师可以讲授两门课程，因此总花费为 $10 + 17 = 27$。

对于第三个样例输入，第一位老师可以讲授两门课程，第二位老师可以讲授三门课程，因此总花费为 $20 + 37 = 57$。