K1o0n принял альтернативный исход и устроился на кафедру программирования. Как известно, все программисты умеют копать траншеи для проводов, поэтому первым же поручением ему досталась проводка между корпусами университета — со счастливым правом сбывать старьё самостоятельно.

В университете $$$n$$$ корпусов, и между некоторыми парами протянуты кабели — всего их $$$m$$$. По $$$i$$$-му кабелю данные ходят в обе стороны, он соединяет корпуса $$$u_i$$$ и $$$v_i$$$, а меди в нём на $$$d_i$$$ монет. Сеть тянули задолго до K1o0n и денег не считали: где-то повесили лишнюю перемычку, где-то взяли кабель подороже, а до каких-то корпусов руки так и не дошли.

Перекроить сеть можно ровно в таком порядке:

1. Снять любое подмножество кабелей. Медь снятого $$$i$$$-го кабеля уходит в приёмку и приносит $$$d_i$$$ монет; связи по этому кабелю больше нет.
2. Протянуть любое количество новых кабелей между любыми двумя различными корпусами. Траншеи K1o0n роет сам, а вот кабель тянет монтажная бригада, и аппетит у неё растёт с каждой заявкой: первый новый кабель обойдётся в $$$x$$$ монет, второй — в $$$2x$$$, третий — в $$$3x$$$, и так далее.

После этого сеть обязана быть связной: из любого корпуса данные должны доходить до любого другого. Обратите внимание, что изначально сеть может быть несвязной.

Прибыль — это выручка от сданной меди минус траты на монтаж.

Вам даются $$$q$$$ сценариев, в $$$j$$$-м сценарии шаг подорожания монтажа равен $$$x_j$$$. Для каждого сценария вам нужно посчитать максимальную прибыль.