Боб играет в игру «Космический Солитер». Цель этой игры — построить космический корабль, но для ее достижения требуется сначала собрать достаточное количество ресурсов $$$n$$$ типов, пронумерованных от $$$1$$$ до $$$n$$$. Боб должен собрать не менее $$$a_i$$$ единиц $$$i$$$-го ресурса. Для удобства назовем $$$a_i$$$ целью для ресурса $$$i$$$.

Для производства одной единицы любого ресурса нужно потратить $$$1$$$ ход (и каждый ход можно производить только один ресурс). Однако для ускорения игры в ней введена система достижений. Каждое достижение описывается тройкой $$$(s_j, t_j, u_j)$$$ и обозначает следующее: как только Боб соберет $$$t_j$$$ единиц ресурса $$$s_j$$$, он сразу же получит дополнительную единицу ресурса $$$u_j$$$, не тратя ход на ее производство. Возможно, награда за достижение позволит активировать другое достижение — таким образом за один ход можно набрать большое количество разных ресурсов.

Система достижений устроена таким образом, что не существует двух достижений, у которых одновременно одинаковые $$$s_j$$$ и $$$t_j$$$. То есть за достижение $$$t_j$$$ единиц ресурса $$$s_j$$$ нельзя получить в награду более одного ресурса.

Ни один бонусный ресурс не дается за достижение $$$0$$$ единиц какого-либо ресурса. Также не существует достижений, для которых надо собрать $$$a_i$$$ или более соответствующего ресурса. Формально, $$$0 < t_j < a_{s_j}$$$.

Могут существовать достижения, для которых тип требуемого ресурса совпадает с типом бонусного ресурса, то есть $$$s_j = u_j$$$.

Изначально в игре нет достижений. Вам нужно обработать $$$q$$$ обновлений игры, каждое из которых добавляет, удаляет или меняет какое-то достижение. После каждого обновления посчитайте минимальное количество ходов, требуемое для завершения игры (то есть для того, чтобы собрать не менее $$$a_i$$$ единиц $$$i$$$-го ресурса для всех $$$i \in [1, n]$$$).