P1064 [NOIP 2006 Senior] Jinming’s Budget Plan

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.

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 a single integer on one line representing the answer.

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