3978: Sky 不会计数
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：8
解决：1
题目描述
number.cpp/in/out
大样例
Sky 不会计数，但是他很喜欢计数。
Sky 给了你一张有 $n$ 个点 $m$ 条边的有向图，每个点上有点权， $w_i$ 表示第 $i$ 个点上的点权。
同时他还给了你一个计数器 $A$ 以及一个正整数 $T$。Sky 想要让计数器的值在任何时刻都不小于 $0$ 或者大于 $T$。
计数器初始时值为 $0$。
之后你可以在有向图上任意选择一条路径，当你每一次到达一个点 $i$ 的时候，都可以进行以下操作之一：
- 不操作
- 为计数器加上 $w_i$
- 为计数器减去 $w_i$
Sky 想知道你可以让计数器达到的最大值是多少。
大样例
Sky 不会计数，但是他很喜欢计数。
Sky 给了你一张有 $n$ 个点 $m$ 条边的有向图，每个点上有点权， $w_i$ 表示第 $i$ 个点上的点权。
同时他还给了你一个计数器 $A$ 以及一个正整数 $T$。Sky 想要让计数器的值在任何时刻都不小于 $0$ 或者大于 $T$。
计数器初始时值为 $0$。
之后你可以在有向图上任意选择一条路径，当你每一次到达一个点 $i$ 的时候，都可以进行以下操作之一：
- 不操作
- 为计数器加上 $w_i$
- 为计数器减去 $w_i$
Sky 想知道你可以让计数器达到的最大值是多少。
输入
本题采用多组测试数据
第一行两个整数 $Ta, id$，表示数据组数与当前数据点编号。
你可能并不需要用到 $id$，这时你可以只读入 $id$ 不处理它。
之后会按照如下方式输入 $Ta$ 组数据。
第一行三个整数 $n, m, T$。
之后一行 $n$ 个整数，第 $i$ 个整数代表 $w_i$。
之后 $m$ 行，每行两个整数 $a_i,b_i$，表示在 $ $a_i,b_i$
第一行两个整数 $Ta, id$，表示数据组数与当前数据点编号。
你可能并不需要用到 $id$，这时你可以只读入 $id$ 不处理它。
之后会按照如下方式输入 $Ta$ 组数据。
第一行三个整数 $n, m, T$。
之后一行 $n$ 个整数，第 $i$ 个整数代表 $w_i$。
之后 $m$ 行，每行两个整数 $a_i,b_i$，表示在 $ $a_i,b_i$
输出
对于每组数据，输出计数器能达到的最大值。
样例输入 复制
1 0
6 6 5
2 1 2 1 1 1
4 2
1 2
1 5
2 5
5 3
5 6样例输出 复制
5提示
