Алгоритмы

Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию вошли все воины каждого из n городов его королевства. Петир выяснил, что в i-м городе ищут работу a_i воинов, которых он может завербовать в свою армию.

Исходно в армии Лорда нет ни одного воина. Чтобы воин вошел в армию, Петир может заплатить этому воину. Для вербовки одного воина из i-го города, необходимо заплатить ему c_i золотых монет. При этом воины из больших городов ценят свою работу дороже, поэтому если для i-го и j-го города выполнено a_i < a_j , то ci ≤ c_j . Однако есть еще один способ добиться того, чтобы воины присоединились к армии. Если в какой-то момент оказывается, что в армии Лорда Петира уже строго больше воинов, чем осталось в некотором городе, то все воины этого города бесплатно присоединяются к армии Лорда.
Помогите Лорду Петиру выяснить, какое минимальное количество золотых монет он должен заплатить воинам, чтобы все воины из всех городов оказались в его армии.

Входные данные

В первой строке входного файла находится целое число n (1 ≤ n ≤ 1000) — количество городов, в которых Лорд Петир намерен набирать себе воинов. В следующих n строках входного файла находится по два целых числа a_i и c_i (1 ≤ a_i ≤ 100, 1 ≤ c_i ≤ 10 000) — количество воинов в i-м городе и число монет, которое необходимо заплатить одному воину в этом городе, чтобы он присоединился к армии. Для всех пар i и j выполнено условие, что если a_i < a_j , то c_i ≤ c_j .

Выходные данные

В выходной файл выведите одно целое число — минимальное количество монет, которые Лорду Петиру придется заплатить, чтобы все воины вошли в его армию.

В приведенном примере Лорду необходимо действовать следующим образом. Сначала он платит 2 монеты воину из второго города, и 3 монеты воину из третьего города, чтобы они присоединились

к его армии. Теперь в армии Лорда 2 воина, а в городах осталось 1, 1 и 3 воина, соответственно. Воины из первого и второго городов бесплатно присоединяются к армии Лорда Петира, в его армии становится 4 воина, после чего и оставшиеся 3 воина из третьего города бесплатно присоединяются к его армии.

После посадки на Марс учёные нашли странную систему пещер, соединённых туннелями. И учёные начали исследовать эту систему, используя управляемых роботов. Было обнаружено, что существует ровно один путь между каждой парой пещер. Но потом учёные обнаружили специфическую проблему. Иногда в пещерах происходят небольшие взрывы. Они вызывают выброс радиоактивных изотопов и увеличивают уровень радиации в пещере. К сожалению, роботы плохо выдерживают радиацию. Но для исследования они должны переместиться из одной пещеры в другую. Учёные поместили в каждую пещеру сенсор для мониторинга уровня радиации.  Теперь они каждый раз при движении робота хотят знать максимальный уровень радиации, с которым придётся столкнуться роботу во время его перемещения. Как вы уже догадались, программу, которая это делает, будете писать вы.

Формат входных данных
Первая строка содержит одно целое число N (1≤ N ≤ 100000) — количество пещер. Следующие N −1 строк описывают туннели. Каждая из этих строк содержит два целых числа — a_i и b_i (1 ≤ a_i,b_i ≤ N), описывыющие туннель из пещеры с номером a_i в пещеру с номером b_i. Следующая строка содержит целое число Q (1 ≤ Q ≤ 100000), означающее количество запросов. Далее идут Q запросов, по одному на строку. Каждый запрос имеет вид «C U V », где C — символ «I» либо «G», означающие тип запроса (кавычки только для ясности). В случае запроса «I» уровень радиации в U-й пещере (1 ≤ U ≤ N) увеличивается на V (0 ≤ V ≤ 10000). В случае запроса «G» ваша программа должна вывести максимальный уровень радиации на пути между пещерами с номерами U и V (1≤ U,V ≤ N) после всех
увеличений радиации (запросов «I»), указанных ранее. Предполагается, что изначальный уровень радиации равен 0 во всех пещерах, и он никогда не уменьшается со временем (потому что период полураспада изотопов много больше времени наблюдения).
Формат выходных данных
Для каждого запроса «G» выведите одну строкусодержащую максимальный уровень радиации