Shopping List Optimization

Jinming is excited about moving into his new home and has been given a budget limit of \(n\) yuan to spend on decorating his room. He plans to purchase several items, each with a price (a multiple of 10) and an importance rating from 1 to 5, where 5 indicates the highest priority. The items are divided into two categories: main items and accessories. An accessory item can only be purchased if its corresponding main item is bought. Each main item can have 0, 1, or 2 accessories.

If Jinming decides to buy \(k\) items with prices \(v_{j_1}, v_{j_2}, \dots, v_{j_k}\) and importance ratings \(w_{j_1}, w_{j_2}, \dots, w_{j_k}\), the total score is calculated as:

[ \sum_{i=1}^{k} v_{j_i} \times w_{j_i} ]

The goal is to choose a set of items such that the total cost does not exceed \(n\) yuan, while maximizing the total score. Note that if an accessory is chosen, its main item must be included as well.

inputFormat

The first line contains two integers: \(n\) (the available budget, in yuan) and \(m\) (the number of items).

Each of the following \(m\) lines contains three integers: \(v\), \(w\), and \(q\), where:

• \(v\) is the price of the item (in multiples of 10 yuan),
• \(w\) is the importance of the item (an integer from 1 to 5),
• \(q = 0\) indicates that the item is a main item; otherwise, the item is an accessory to the main item with index \(q\).

outputFormat

Output a single integer representing the maximum achievable total score multiplied by 10 (since prices are in multiples of 10). The total score is defined as:

[ \sum v_j \times w_j ]

where the sum is taken over all selected items and the total cost does not exceed \(n\) yuan.

sample

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

2200