SPOJ in Armenian

Մանկական տոնի կազմակերպիչները պլանավորել են տոնական միջոցառման ժամանակ փչել M հատ փուչիկ։ Այդ նպատակով նրանք հրավիրել են N կամավոր օգնականների, որոնցից i-րդը մի փուչիկը փչում է Ti րոպեում, սակայն ամեն անգամ Zi փուչիկ փչելուց հետո հոգնում է և հանգստանում է  Yi րոպե։ Այժմ տոնի կազմակերպիչները ուզում են իմանալ, թե օգնականների ամենաօպտիմալ աշխատանքի դեպքում քանի րոպե անց աշխատանքը կավարտվի։ (Եթե որևէ օգնականի հանգստանալուց հետո էլ ոչ մի փուչիկ չի մնացել փչելու, համարվում է, որ նա իր աշխատանքն ավարտել է անմիջապես վերջին փուչիկը փչելուց հետո, ոչ թե հանգստանալուց հետո)։

Մուտքը

Առաջին տողում տրված են M և N թվերը (0 ≤ M ≤ 1000, 1 ≤ N ≤ 20)։ Հաջորդ  N տողերը պարունակում են երեքական թիվ - Ti, Zi և Yi համապատասխանաբար (1 ≤ Ti, Yi ≤ 100, 1 ≤ Zi ≤ 1000)։

Ելքը

Ելքում արտածեք T մինիմալ ժամանակը, որի ընթացքում կփչվեն բոլոր փուչիկները։

Օրինակ

Մուտքը.
10 3
1 2 3
3 10 3
2 4 3

Ելքը.
8

Խնդիրը օգտագործվել է 2003 թ ընտրական փուլում։