Jinming's Budget Plan

Problem Background

Special for beginners, ^_^

Problem Description

Jinming is very happy today: his family's new house is about to get its keys, and he has a spacious room of his own. Even better, his mother told him yesterday: "You decide what items to buy for your room and how to arrange it, as long as it doesn't exceed $N$ yuan." Early this morning Jinming started budgeting. He divides the items he wants to buy into two categories: main items and accessories. An accessory belongs to a main item; examples:

To buy an accessory, you must first buy its main item. Each main item may have 0, 1, or 2 accessories. Accessories have no accessories of their own. Jinming wants to buy many things, surely exceeding the $N$ yuan limit. So he assigned each item an importance from 1 to 5 (5 is most important). He also found each item's price online (all multiples of 10 yuan). He wants, without exceeding $N$ yuan (it may equal $N$), to maximize the sum of (price × importance) over all selected items.

Let the price of item $j$ be $v[j]$ and its importance be $w[j]$; $k$ items are selected, numbered $j_1,j_2,\dots,j_k$. The desired sum is:

$v[j_1]\ast w[j_1]+v[j_2]\ast w[j_2]+\dots+v[j_k]\ast w[j_k]$. (where $\ast$ denotes multiplication)

Please help Jinming design a shopping list that meets the requirements.

Input Format

The first line contains two positive integers separated by a space:

N m (where $N\ (<32000)$ is the total budget and $m\ (<60)$ is the number of items to consider).

From line 2 to line $m+1$, line $j$ gives the basic data of item numbered $j-1$, with three non-negative integers per line: v p q (where $v$ is the price ($v<10000$), $p$ is the importance ($1\sim 5$), $q$ indicates whether the item is a main item or an accessory. If $q=0$, it is a main item; if $q>0$, it is an accessory whose owner main item is number $q$).

Output Format

Output a single positive integer — the maximum value of the sum of (price × importance) of selected items not exceeding the total budget ($<200000$).

Sample Input

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

Sample Output

2200

Constraints

Time limit 1s, memory limit 1024KiB for each test case.