Фениксу стало интересно: какого это — красть бриллианты из ювелирного магазина!
Всего есть \(n\) видов бриллиантов: бриллиант \(i\)-го вида весит \(w_i\) и стоит \(v_i\). Первоначально в магазине есть \(a_i\) бриллиантов \(i\)-го вида.
Каждый день, на протяжении \(q\) дней, происходит одно из следующих событий:
- В магазин поступает \(k_i\) бриллиантов вида \(d_i\).
- Магазин продает \(k_i\) бриллиантов вида \(d_i\).
- Феникс интересуется, что произойдет, если он решит ограбить магазин, придя в него с мешком, который может вместить бриллианты суммарным весом не более \(c_i\). Если Феникс будет брать бриллианты жадно начиная с самых дорогих, бриллиантов на какую стоимость он наберет? Если есть несколько бриллиантов с максимальной стоимостью, он будет брать сначала самые легкие. Если же среди бриллиантов с максимальной стоимостью есть несколько с минимальным весом, то он берет любой из них.
Конечно же, так как Феникс — законопослушный гражданин, то все описанное выше — не более чем мысленный эксперимент и он никогда не будет по-настоящему забирать бриллианты из магазина. Другими словами, запросы типа \(3\) не влияют на количество бриллиантов в магазине.
Выходные данные
Выведите ответ для каждого запроса третьего типа (\(t=3\)).
Примечание
В первом запросе с \(t=3\), Феникс может уместить \(2\) бриллианта вида \(1\), с общим весом \(6\) и стоимостью \(8\).
Во втором запросе с \(t=3\), Феникс может забрать \(3\) бриллианта вида \(3\) и еще один вида \(1\). Общий вес будет равен \(9\), а стоимость — \(16\). Заметим, что бриллианты вида \(3\) предпочтительнее, чем вида \(1\), потому что вид \(3\) при равной стоимости имеет меньший вес.
В последнем запросе с \(t=3\), Феникс может забрать все бриллианты с общей стоимостью \(13\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
2 3 4
1 5 1
0 2 4
3 6
1 3 3
3 10
2 2 3
3 30
|
8
16
13
|