题目来自 CCSP2026 T2，评测使用官方数据和自造高质量复刻数据。我们承认原始题面、大样例、官方数据版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

大语言模型 Agent 在处理复杂任务时，通常不会只进行一次模型推理。一个完整的 Agent 工作流可能包含很多相互依赖的任务，例如：

• 分析用户请求；
• 检索不同的数据源；
• 调用工具并读取工具输出；
• 根据前面的结果继续推理；
• 汇总所有中间结果，生成最终回答。

这些任务之间可能存在依赖关系。例如，只有在“检索文档”完成后，才能执行“总结文档”；只有在多个子任务都完成后，才能进行最终汇总。因此，一个 Agent 工作流可以表示成一张有向无环图（DAG）。本题假设运行平台采用统一内存架构（Unified Memory Architecture），CPU 与 GPU 共享同一内存空间，不区分 GPU 显存与内存。

执行某个 Agent 任务时，系统可能进行模型推理、检索文档或运行工具，并占用相应的工作内存。任务完成后，大部分临时内存可以立刻释放，但任务结果、工具输出和可复用的 KV Cache 等仍需保留在内存中，以供后续任务和最终汇总使用。当多个任务都已经满足依赖条件时，Agent 调度器可以自行决定先执行哪个任务。不同的执行顺序不会改变每个任务的结果，却会显著影响工作流执行期间的峰值内存占用。

题目描述

一个 Agent 工作流包含 $n$ 个任务，编号为 $1, 2, \ldots, n$。系统串行执行这些任务，任意时刻最多执行一个任务。任务一旦开始，就会连续执行到完成，不会被暂停或抢占。

第 $i$ 个任务有两个非负整数参数，保证 $0 \le S_i \le P_i$：

• $P_i$：执行任务 $i$ 期间，除此前任务已保留的内存外，该任务占用的最大内存；
• $S_i$：任务 $i$ 完成后，由该任务新增的保留内存，包括任务结果、工具输出和可复用的 KV Cache 等。

具体地，假设执行任务 $i$ 之前，已完成任务共占用的内存大小为 $X$，那么：

1. 执行任务 $i$ 的过程中，内存占用峰值达到 $X + P_i$；
2. 任务 $i$ 完成后，它的临时内存被释放，但会留下大小为 $S_i$ 的保留内存；
3. 因此任务完成后，已经保留的内存总量变为 $X + S_i$。

在本题的简化模型中，为了支持后续任务、最终结果汇总和执行过程审计，任何任务完成后留下的 $S_i$ 个内存单元都必须保留到整个工作流结束，不能提前释放，也不能换出到其他存储设备。

任务之间有 $m$ 条依赖边。有向边 $u \to v$ 表示任务 $v$ 依赖任务 $u$ 的结果，因此任务 $u$ 必须在任务 $v$ 之前完成。输入保证所有依赖关系组成一张有向无环图。只要一个尚未执行的任务的所有前驱任务都已经完成，调度器就可以选择执行它。

一个合法调度是任务编号的一个排列 $\pi_1, \pi_2, \ldots, \pi_n$，并且对于每条依赖边 $u \to v$，$u$ 在排列中都出现在 $v$ 之前。也就是说，合法调度就是依赖图的一个拓扑序。

对于一个合法调度 $\pi_1, \pi_2, \ldots, \pi_n$，在执行第 $k$ 个任务 $\pi_k$ 之前，前面已经完成的任务留下的内存总量为：

$$\sum_{j=1}^{k-1} S_{\pi_j}.$$

因此，执行任务 $\pi_k$ 时的内存峰值为：

$$P_{\pi_k} + \sum_{j=1}^{k-1} S_{\pi_j}.$$

整个调度过程的峰值内存定义为：

$$M(\pi) = \max_{1 \le k \le n} \left(P_{\pi_k} + \sum_{j=1}^{k-1} S_{\pi_j}\right).$$

你需要在所有合法调度中，求出最小可能的峰值内存：

$$\min_{\pi} M(\pi).$$

本题只要求输出最小峰值内存，不要求输出具体的任务执行顺序。

输入格式

从标准输入读入数据。

第一行包含两个整数 $n, m$，分别表示任务数量和依赖边数量。

接下来 $n$ 行，第 $i$ 行包含两个整数 $P_i$ 和 $S_i$，描述任务 $i$ 的运行期额外内存峰值和完成后需要保留的内存大小。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示一条依赖边 $u \to v$，即任务 $u$ 必须在任务 $v$ 之前完成。

输入保证依赖图中没有自环和重边，并且依赖图是一张有向无环图。

输出格式

输出到标准输出。

输出一行，包含一个整数，表示所有合法调度中最小可能的峰值内存。

4 3
8 3
6 5
7 1
2 2
1 4
2 4
3 4

11

样例 1 解释

任务 $4$ 依赖任务 $1, 2, 3$，因此前三个任务必须全部完成后才能执行任务 $4$。

一种最优调度为：

3 1 2 4

各任务执行时的内存情况如下：

执行任务	执行前已保留内存	任务自身峰值 $P_i$	执行时总峰值	完成后已保留内存
3	0	7	7	1
1	1	8	9	4
2	4	6	10	9
4	9	2	11	11

所以该调度的峰值内存为 $11$，并且不存在峰值更小的合法调度。

3 1
110 100
1 1
100 0
2 3

111

样例 2 解释

任务 $3$ 依赖任务 $2$，任务 $1$ 与另外两个任务之间没有依赖关系。

如果按照以下顺序执行：

1 2 3

三个任务执行时的总内存峰值依次为：

$$110, \quad 100 + 1 = 101, \quad 100 + 1 + 100 = 201.$$

整个过程的峰值为 $201$。

而按照以下顺序执行：

2 3 1

三个任务执行时的总内存峰值依次为：

$$1, \quad 1 + 100 = 101, \quad 1 + 110 = 111.$$

因此最小峰值内存为 $111$。

子任务

对于所有测试数据，保证 $1 \le n \le 2 \times 10^5,\ 0 \le m \le 2 \times 10^5,\ 0 \le S_i \le P_i \le 10^9$。输入保证依赖图为有向无环图。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务	分值	特殊限制
1	10	$n \le 10$
2		依赖图是一条链
3	15	依赖图是一棵有根星形树，所有叶子任务都直接指向根任务
4		依赖图是一棵有根二叉树，每条边都从孩子指向父亲
5	20	依赖图是一棵有根树，每条边都从孩子指向父亲
6	30	无

对于子任务 2，忽略边的方向后，依赖图是一条链，并且边的方向保证整张图只有一个拓扑序。

对于子任务 3、4、5，根任务没有后继；除根外的每个任务都恰好有一条指向其父任务的边。因此，父任务必须等待其所有孩子任务完成。