Description

Jinming is very happy today because his family is about to receive the keys to their new home, which has a spacious room just for him. What makes him even happier is that his mother told him yesterday: “You can decide what to buy and how to arrange your room, as long as it doesn’t cost more than $n$ yuan.” Early this morning, Jinming started budgeting. He divides the items he wants to buy into two categories: main items and accessories. Accessories belong to a specific main item. The table below shows some examples of main items and accessories:

Main Item	Accessory
Computer	Printer, scanner
Bookcase	Books
Desk	Desk lamp, stationery
Office chair	None

To buy an item classified as an accessory, you must first buy its corresponding main item. Each main item can have $0$, $1$, or $2$ accessories. Each accessory corresponds to one main item, and accessories do not have accessories of their own. Jinming wants to buy many things, and surely the total will exceed $n$ yuan. So he assigns an importance level to each item, divided into $5$ levels represented by integers $1$ to $5$, with level $5$ being the most important. He also found the price of each item on the Internet (all prices are multiples of $10$ yuan). He wants to maximize the sum of the product of price and importance for the selected items without exceeding $n$ yuan.

Let the price of the $j$-th item be $v_j$ and its importance be $w_j$. Suppose $k$ items are selected, with indices $j_1, j_2, \dots, j_k$. The target sum is:

$$v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2}+ \dots +v_{j_k} \times w_{j_k}$$

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

Input Format

The first line contains two integers, the total budget $n$ and the number of items $m$.

For lines $2$ to $m + 1$, each line contains three integers. On the $(i + 1)$-th line, the integers $v_i$, $p_i$, $q_i$ denote the price, importance, and the index of its main item for the $i$-th item, respectively. If $q_i = 0$, it means the item itself is a main item.

Output Format

Output a single integer on one line representing the answer.

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

2200

Hint

Constraints

For all test points, it is guaranteed that $1 \leq n \leq 3.2 \times 10^4$, $1 \leq m \leq 60$, $0 \leq v_i \leq 10^4$, $1 \leq p_i \leq 5$, $0 \leq q_i \leq m$, and the answer does not exceed $2 \times 10^5$.

NOIP 2006 Senior, Problem 2.

Translated by ChatGPT 5