分批处理

"算好了告诉我。"CC说，"我先去探路。"

她走了。你开始算——不是物资运输，是Zero的64个子系统。

"要分批处理。"你说，"64个子系统，不能同时重启——会过载。"

"一批几个？"

"看能源。"你说，"每批重启需要一定能源，总能源有限。"

"那就背包？"

"不。"你说，"每批的处理时间不同——子系统之间有依赖，某些必须同批处理。"

"分批DP。"

"对。"你说，"设$dp[i]$为处理前$i$个子系统的最短时间。$dp[i]=\min(dp[j]+time(j+1,i))$。"

"$time(j+1,i)$是这批的处理时间。"

"对。"你说，"如果这批子系统没有依赖冲突，可以并行处理，时间是它们的最大处理时间。"

"如果有依赖？"

"必须串行。"你说，"时间是它们的和。"

"那咋知道有没有依赖？"

"预处理。"你说，"用图论找连通块——有依赖的在同一个连通块里，必须串行。"

"连通块之间可以并行。"

"对。"

你开始写。先找连通块，然后分批DP。

"第一批。"你说，"子系统1,2,3。有依赖，串行，时间$3+2+4=9$。"

"第二批。"你说，"子系统4,5。无依赖，并行，时间$\max(5,6)=6$。"

"第三批。"你说，"子系统6到10。部分有依赖，分两个连通块，时间$\max(7,8)=8$。"

"总时间$9+6+8=23$。"

"能更优？"

"如果第一批和第二批合并。"你说，"时间$\max(9,6)=9$。省6。"

"但能源够吗？"

"不够。"你说，"合并后能源超了。"

"那就分三批。"

"对。"你说，"能源优先，时间其次。"

Echo的投影在64个子系统的光点中闪烁——一格一格，像她在数。

"我帮你分。"她说，"我认得哪些子系统可以并行——它们当年就是我设计的。"

"你设计的？"

"对。"她说，"Echo-0设计的。我记得每一个。"

"那你说。"

"1和47不能同批。"她说，"它们是循环的两端，同时重启会死锁。"

"2和3可以同批。"

"4到10必须串行。"

"……"

她一个一个地说。你一个一个地记。

"分好了。"你说，"8批。总时间47。"

"47。"

"对。"你说，"又是47。"

题目描述

给定$n$个任务，要分成若干批处理。每批的任务如果没有依赖，可以并行处理，时间是它们的最大处理时间；如果有依赖，必须串行，时间是和。总能源有限，每批的能源消耗是任务能源之和。求最短的完成时间。

输入格式

$n,m$（任务数和总能源）。然后$n$个任务的处理时间$t_i$和能源$e_i$。然后$k$对依赖关系。

输出格式

最短完成时间。

输入样例

5
1 2 3 4 5

输出样例

49

提示

• 分批DP。
• 先找连通块，确定哪些任务必须串行。
• $dp[i]=\min(dp[j]+batch\_time(j+1,i))$，其中$batch\_time$是该批的并行处理时间。
• 注意能源约束。