In the Bermart chain of stores, a variety of ice cream is sold. Each type of ice cream has two parameters: price and tastiness.
Initially, there is one store numbered $$$1$$$, which sells nothing. You have to process $$$q$$$ queries of the following types:
The first line contains a single integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^4$$$) — the number of queries.
Each of the following $$$q$$$ lines contains a query in the format described in the statement:
Additional constraints on the input data:
For each query of type $$$4$$$, output a single integer — for store $$$x$$$, find the maximum total tastiness of a subset of types of ice cream that are sold there, such that the total price does not exceed $$$p$$$ (each type can be used in the subset no more than once).
122 1 5 72 1 3 44 1 44 1 84 1 21 12 2 4 104 1 94 2 93 14 1 94 2 9
4 11 0 11 17 4 17
Name |
---|