You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

农夫约翰有 $N$ 头奶牛（$1 \leq N \leq 10^4$），编号为 $1$ 到 $N$。每头奶牛 $i$ 挤奶需要 $T_i$ 单位时间。由于牛棚的布局限制，某些奶牛必须在其他奶牛之前完成挤奶。例如，若奶牛 $A$ 必须在奶牛 $B$ 之前挤奶，则 $A$ 必须完全挤奶完成后，才能开始挤奶 $B$。

为了尽快完成挤奶，约翰雇用了大量工人，可以同时为任意多头奶牛挤奶。但由于存在先后顺序约束，整个挤奶过程仍需遵循特定顺序。请计算挤奶过程的最短总时间。

输入格式

• 第一行：两个整数 $N$（奶牛数量）和 $M$（约束条件数量，$1 \leq M \leq 5\times 10^4$）。
• 第 $2$ 至 $N+1$ 行：每行一个整数 $T_i$，表示第 $i$ 头奶牛的挤奶时间（$1 \leq T_i \leq 10^5$）。
• 第 $N+2$ 至 $N+M+1$ 行：每行两个整数 $A$ 和 $B$，表示奶牛 $A$ 必须完全挤奶后，才能开始挤奶牛 $B$。所有约束条件不会形成循环，保证有解。

输出格式

• 一行：输出完成所有挤奶的最短总时间。

3 1 
10 
5 
6 
3 2 

11 

提示

共有 $3$ 头奶牛，挤奶时间分别为 $10,5,6$。奶牛 $3$ 必须在奶牛 $2$ 之前完成挤奶。

初始时，奶牛 $1$ 和 $3$ 可同时挤奶（耗时 $10$ 和 $6$）。奶牛 $3$ 完成后，开始挤奶牛 $2$（总耗时 $6 + 5 = 11$）。