Dynamic planning, shopping list problem

describe

Wang Qiang decided to use the year-end bonus for shopping , He divided the items he wanted to buy into two categories ： Main parts and accessories , The attachment is subordinate to a main component , Here are some examples of main components and accessories ：

Main parts	The attachment
The computer	The printer , Scanner
Bookcase	The book
desk	Desk lamp , Stationery
Work chair	nothing

If you want to buy items classified as accessories , You must buy the main part of the accessory first , And each item can only be purchased once .

Each main component can have  0  individual 、 1  Or  2  Attachments . Attachments no longer have their own attachments .

Wang Qiang found the price of each item （ All are  10  An integral multiple of one yuan ）, And he only N Yuan budget . besides , He set an importance level for each item , Integers  1 ~ 5  Express . He hopes to spend no more than  N  Under the premise of yuan , Maximize your satisfaction .

Satisfaction refers to the sum of the product of the price and importance of each item purchased , Let's assume that ii The price of the item is v[i]v[i], The importance is w[i]w[i