В сети магазинов Бермарт продается мороженое. У каждого сорта мороженого есть два параметра: цена и вкусность.
Изначально есть один магазин с номером \(1\), в котором ничего не продаётся. Требуется обработать \(q\) запросов следующих типов:
- \(1~x\) — открывается новый магазин, в котором продаются те же сорта мороженого, что и в магазине \(x\). Он получает первый свободный порядковый номер. Порядок появления сортов мороженого в новом магазине тот же, что и в магазине \(x\).
- \(2~x~p~t\) — в магазине \(x\) в продаже появляется сорт мороженого с ценой \(p\) и вкусностью \(t\).
- \(3~x\) — в магазине \(x\) исчезает из продажи сорт мороженого, который там появился раньше всего.
- \(4~x~p\) — для магазина \(x\) надо найти максимальную суммарную вкусность поднабора сортов, которые там продаются, так, чтобы суммарная цена не превышала \(p\) (каждый сорт можно использовать в поднаборе не более одного раз).
Выходные данные
На каждый запрос типа \(4\) выведите одно целое число — для магазина \(x\) найдите максимальную суммарную вкусность поднабора сортов, которые там продаются, так, чтобы суммарная цена не превышала \(p\) (каждый сорт можно использовать в поднаборе не более одного раз).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12
2 1 5 7
2 1 3 4
4 1 4
4 1 8
4 1 2
1 1
2 2 4 10
4 1 9
4 2 9
3 1
4 1 9
4 2 9
|
4
11
0
11
17
4
17
|