U143772 wjyyy发床单

wjyyy是一个有着很多很多床单的小姐姐

wjyyy因为床单太多了，所以她想要分给她的所有好友，当然，只是给他们看而已 wjyyy有$n$个朋友 不妨将他们从$1$到$n$编号 每个人都可以把他手上的床单给一部分他认识的人 但是很不幸的是 大部分人都是舔狗 也就是说他认识的人有可能不会把床单给他 当然 出于现实原因 每当一条床单从某个人手里传递到另一个人手里时 会花上一些钱 由于wjyyy非常喜欢床单 所以你要求出wjyyy最少用几条床单就可以让所有人都得到过她的床单 同时 wjyyy是魔法少女 所以wjyyy的床单没有必要传递回wjyyy 最后wjyyy会使用魔法来收回她的床单 不过wjyyy没有钱 所以你需要求出最少需要花多少钱

第一行一个整数$n$ 表示wjyyy朋友的数量 之后一行$n$个整数 第$i$个整数$w_i$表示wjyyy向$i$这个人传递床单需要的钱$C_{0,i}$ 之后$n$行 第$i+2$行由一个整数$x_i$开始 之后的$2\times x_i$个整数 每两个描述了一个关系 其中第一个整数描述了可能的传递方向 第二个整数描述了传递一张床单时需要消耗的钱$C_{i,j}$

输出一行一个整数表示wjyyy在床单使用的最少的情况下的花的最少的钱的数量

样例如图： 在这个情况下 床单的传递路线为 wjyyy -> 1 -> 2 -> 3 -> 4 容易计算出此时的最小费用为12 我们令$m=\sum_{i=1}^nx_i$ 之后我们给出本题的数据范围： $n\leq 300,m\le 10000,0\le w_i,C_{i,j}\le 1000$