Вы наконец-то осуществили свою давнюю мечту и оказались в Мэйбилэнде, но радоваться пока что рано. Теперь вам предстоит быстро адаптироваться к новому месту и действовать согласно установленным в этом волшебном городе порядкам, иначе вас быстро раскусят местные жители. Первое, с чем вам предстоит разобраться — необычная система передвижения.

Мэйбилэнд представляет собой $$$n$$$ замков, пронумерованных от $$$1$$$ до $$$n$$$ и соединенных $$$n - 1$$$ тропинкой, при этом гарантируется, что по тропинкам можно добраться от любого замка до любого другого замка. Проще говоря, Мейбилэнд является деревом.

В момент времени $$$1$$$ вы находитесь в замке с номером $$$1$$$. За одну мэйби-минуту вы можете переместиться из текущего замка в любой другой замок, с которым текущий соединен тропинкой. Обратите внимание, что перемещение обязательно должно произойти, то есть, остаться в том же замке в следующий момент времени вы не можете.

Также вы знаете, что $$$m$$$ раз случится чудо и в замке с номером $$$v_i$$$ в момент времени $$$t_i$$$ окажется вкусный леденец, соответственно, если в момент $$$t_i$$$ вы оказались в замке $$$v_i$$$, то вы можете забрать вкусный леденец с собой. Учтите, что по истечении момента времени $$$t_i$$$ вкусный леденец исчезает, и если вы не успели его забрать, то у вас больше не будет возможности взять его снова.

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