题目内容

在大规模深度学习训练中，常采用流水线并行（Pipeline Parallelism）来提升训练效率。模型被划分为多个连续阶段（stage），每个阶段在不同设备上执行。合理的阶段划分需要兼顾：

• 计算负载均衡
• 通信开销最小

给定一个包含 n 层的模型，需要按顺序划分为 p 个连续阶段。每层有计算时间 time[i]，相邻层之间存在通信开销 comm[i]。

如果在层 k 与层 k+1 之间划分阶段，需要产生通信开销 comm[k]。每个阶段的计算时间为该阶段所有层计算时间之和。设：

$stage\_time = \text{某个阶段所有层的 time 之和}$

所有阶段必须满足：

$stage\_time \leq T$

其中 T 为给定的最大阶段计算时间。

在满足上述约束的情况下，需要选择划分方式，使总通信开销最小。若不存在合法划分方案，输出 -1。

输入描述

n p T
time1 time2 ... timen
comm1 comm2 ... comm(n-1)

含义：

• n：模型层数，1 ≤ n ≤ 1000
• p：阶段数量，1 ≤ p ≤ n
• T：单个阶段允许的最大计算时间，1 ≤ T ≤ 100000
• time[i]：第 i 层的计算时间，1 ≤ time[i] ≤ 100
• comm[i]：层 i 与 i+1 之间的通信开销，1 ≤ comm[i] ≤ 10

输出描述

输出一个整数：最小总通信开销。若不存在满足条件的划分方案，输出：-1。

样例1

输入

5 3 10
2 4 6 3 7
1 1 1 1

输出

2

说明

解释：一种合法划分方式为：[2,4] | [6,3] | [7]

阶段计算时间：6, 9, 7，均不超过 T = 10。

划分点在：层2后，层4后。

通信开销：comm[2] + comm[4] = 1 + 1 = 2。

样例2

输入

4 2 7
3 5 4 2
1 2 3

输出

-1

说明

解释：任意划分都会导致某个阶段计算时间大于 7，因此不存在合法方案。

补充说明

提示：

• 模型层必须按原始顺序划分
• 每个阶段至少包含 1 层
• 总共必须划分为恰好 p 个阶段
• 通信开销只在阶段分界处产生