W国的交通呈一棵树的形状。W国一共有n−1个城市和n个乡村,其中城市从1到n−1编号,乡村从1到n编号,且1号城市是首都。
道路都是单向的,本题中我们只考虑从乡村通往首都的道路网络。对于每一个城市,恰有一条公路和一条铁路通向这座城市。
对于城市i,通向该城市的道路(公路或铁路)的起点,要么是一个乡村,要么是一个编号比i大的城市。没有道路通向任何乡村。
除了首都以外,从任何城市或乡村出发只有一条道路;首都没有往外的道路。从任何乡村出发,沿着唯一往外的道路走,总可以到达首都。
W国的国王小W获得了一笔资金,他决定用这笔资金来改善交通。由于资金有限,小W只能翻修n−1条道路。
小W决定对每个城市翻修恰好一条通向它的道路,即从公路和铁路中选择一条并进行翻修。
小W希望从乡村通向城市可以尽可能地便利,于是根据人口调查的数据,小W对每个乡村制定了三个参数,编号为i的乡村的三个参数是ai,bi和ci。假设 从编号为i的乡村走到首都一共需要经过x条未翻修的公路与y条未翻修的铁路,那么该乡村的不便利值为

在给定的翻修方案下,每个乡村的不便利值相加的和为该翻修方案的不便利值。
翻修n−1条道路有很多方案,其中不便利值最小的方案称为最优翻修方案,小W自然希望找到最优翻修方案,请你帮助他求出这个最优翻修方案的不便利值。

第一行为正整数n。
接下来n−1行,每行描述一个城市。其中第i行包含两个数si,ti,si表示通向第i座城市
的公路的起点,ti表示通向第i座城市的铁路的起点。如果si> 0,那么存在一条从第si座城 市通往第i座城市的公路,否则存在一条从第−si个乡村通往第i座城市的公路;ti类似地,如 果ti > 0,那么存在一条从第ti座城市通往第i座城市的铁路,否则存在一条从第−ti个乡村通 往第i座城市的铁路。
接下来n行,每行描述一个乡村。其中第i行包含三个数ai, bi, ci,其意义如题面所示。

输出一行一个整数,表示最优翻修方案的不便利值。

【样例解释1】

如图所示,我们分别用蓝色、黄色节点表示城市、乡村;用绿色、红色箭头分别表示 公路、铁路;用加粗箭头表示翻修的道路。
一种不便利值等于54的方法是:翻修通往城市2和城市5的铁路,以及通往其他城市的公路。用→和⇒表示公路和铁路,用∗→和∗⇒表示翻修的公路和铁路,那么:
编号为1的乡村到达首都的路线为:−1 ∗→ 3 ⇒ 1,经过0条未翻修公路和1条未翻修铁 路,代价为3 × (1 + 0) × (2 + 1) = 9;
编号为2的乡村到达首都的路线为:−2 ⇒ 3 ⇒ 1,经过0条未翻修公路和2条未翻修铁 路,代价为2 × (1 + 0) × (3 + 2) = 10;
编号为3的乡村到达首都的路线为:−3 ∗→ 4 → 2 ∗→ 1,经过1条未翻修公路和0条未 翻修铁路,代价为3 × (2 + 1) × (1 + 0) = 9;
编号为4的乡村到达首都的路线为:−4 ⇒ 4 → 2 ∗→ 1,经过1条未翻修公路和1条未翻修铁路,代价为1 × (2 + 1) × (3 + 1) = 12;
编号为5的乡村到达首都的路线为:−5 → 5 ∗⇒ 2 ∗→ 1,经过1条未翻修公路和0条未翻修铁路,代价为2 × (3 + 1) × (1 + 0) = 8;
编号为6的乡村到达首都的路线为:−6 ∗⇒ 5 ∗⇒ 2 ∗→ 1,经过0条未翻修公路和0条未 翻修铁路,代价为1 × (3 + 0) × (2 + 0) = 6;
总的不便利值为9 + 10 + 9 + 12 + 8 + 6 = 54。可以证明这是本数据的最优解。


【数据范围】
一共20组数据,编号为1 ∼ 20。
对于编号≤ 4的数据,n≤ 20;
对于编号为5 ∼ 8的数据,ai, bi, ci ≤ 5,n ≤ 50;
对于编号为9 ∼ 12的数据,n ≤ 2000;
对于所有的数据,n ≤ 20000,1 ≤ ai, bi ≤ 60,1 ≤ ci ≤ 109,si, ti是[−n, −1] U (i, n − 1]内的整数,任意乡村可以通过不超过40条道路到达首都。

搜索 动态规划 AHOI高中 2018 level9