В сети магазинов Бермарт продается мороженое. У каждого сорта мороженого есть два параметра: цена и вкусность.
Изначально есть один магазин с номером \(1\), в котором ничего не продаётся. Требуется обработать \(q\) запросов следующих типов:
В первой строке записано одно целое число \(q\) (\(1 \le q \le 3 \cdot 10^4\)) — количество запросов.
В каждой из \(q\) следующих строк записан очередной запрос в формате, описанном в условии:
Дополнительные ограничения на входные данные:
На каждый запрос типа \(4\) выведите одно целое число — для магазина \(x\) найдите максимальную суммарную вкусность поднабора сортов, которые там продаются, так, чтобы суммарная цена не превышала \(p\) (каждый сорт можно использовать в поднаборе не более одного раз).
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
2000 ms 1024 Mb Правила оформления программ и список ошибок при автоматической проверке задач