Problems
Biryong, the Pizza King, runs a pizza shop. His shop sells a total of P types of pizzas.
Biryong has a habit: if he doesn’t make pizza, he gets fidgety. So he will make pizzas whether or not there are orders.
When a pizza is made, the i-th pizza has type pᵢ and price mᵢ.
When a pizza order comes in, the shop gives the customer the earliest-made pizza of the requested type.
If there is no pizza of the requested type available, the customer leaves disappointed (the order is ignored).
Given a sequence of N pizza-making and pizza-order events throughout the day, compute the total sales for Biryong’s pizza shop for that day.
Input
The first line contains two integers P and N.
(1 ≤ P ≤ 50, 1 ≤ N ≤ 500,000)
The next N lines describe the events. Each line contains either:
cmdᵢ pᵢ mᵢ— if cmdᵢ = 0, indicating a pizza is made of type pᵢ with price mᵢ.cmdᵢ pᵢ— if cmdᵢ = 1, indicating a pizza order of type pᵢ.
Constraints:
cmdᵢ ∈ {0, 1}
1 ≤ pᵢ ≤ P
1 ≤ mᵢ ≤ 100
Output
Print a single integer: the total sales of the shop for that day.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 30 | |
| #2 | 30 | |
| #3 | 40 | No additional restrictions |
Example
3 9
1 1
0 3 31
0 1 65
0 1 51
1 3
0 1 59
1 1
1 3
0 1 39
96
You must sign in to write code.