问题 E: 商业天才
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：50
解决：13
题目描述
当前有 $N$ 个城市， $M$ 条单向道路 $($ 可以从城市 $x_i$ 走到城市 $y_i$ 且 $x_i < y_i$ $)$，其中第 $i$ 个城市金条的价格是 $A_i$元。
小 $q$ 是个商业天才，现在要求他在一个城市买一个金条并走到另一个城市卖出，问其最大利润是多少？（有且仅选择一个城市买一个金条并走到另一个城市卖出）
小 $q$ 是个商业天才，现在要求他在一个城市买一个金条并走到另一个城市卖出，问其最大利润是多少？（有且仅选择一个城市买一个金条并走到另一个城市卖出）
输入
$ 2 \leq N \leq 200000 $
$ 1 \leq M \leq 200000 $
$ 1 \leq A_i \leq 10^9 $
$ 1 \leq x_i < y_i \leq N $
$ 1 \leq M \leq 200000 $
$ 1 \leq A_i \leq 10^9 $
$ 1 \leq x_i < y_i \leq N $
输出
最大利润
样例输入 复制
3 1
1 100 1
2 3
样例输出 复制
-99
提示
小 $q$ 可以选择任意点为起点。