解题思路

核心思路

把 $n$ 个 Token 段按到达顺序切成若干连续会话，每个会话注入一个此前未用过的专家组。一组只用一次，因此会话之间的组互异；最短会话、容量、组数上限和切换开销都在切分时一并结算。

记 $dp[i][mask]$ 为已经路由完前 $i$ 个 Token 段、已开启专家集合为 $mask$ 时的最大净收益（可暂为负）。枚举下一段会话 $[i+1,r]$ 与未使用的组 $j$，在长度、负载都合法时转移到 $dp[r][mask\cup\{j\}]$。首次会话不扣 $s$，之后每次新开会话扣一次。

最终答案取所有 $dp[n][\cdot]$ 的最大值；若该值小于 $0$ 或不可达，输出 $-1$。

题目内容

某推理集群需要依次把 $n$ 个 Token 段路由到 $m$ 个部署在 NPU 卡组上的专家组。每个 Token 段必须进入恰好一个专家组。

第 $i$ 个 Token 段的负载为 $w_i$，分给第 $j$ 个专家组的亲和收益为 $p_{i,j}$。第 $j$ 个专家组的驻留容量为 $c_j$，激活开销为 $a_j$。

处理规则

一、会话

• 连续分给同一专家组的 Token 段构成一次会话。
• 每个专家组全程至多开启一次会话。
• 每次会话覆盖的 Token 段数不少于 $q$。
• 开启的专家组个数不超过 $k$。

二、容量与开销

• 一次会话内 Token 段的负载之和不能超过该专家组的驻留容量。
• 第 $j$ 个专家组只要开启过会话，支付激活开销 $a_j$。
• 相邻两次会话之间支付切换开销 $s$，首次会话不支付。

三、净收益

记第 $i$ 个 Token 段进入的专家组为 $g_i$，开启过会话的专家组集合为 $S$。净收益拆成三项：

• 亲和收益：$\sum_{i=1}^{n}p_{i,g_i}$，每个 Token 段按它所进的那一组计一次。
• 激活开销：$\sum_{j\in S}a_j$，每个开启过的专家组扣一次 $a_j$。
• 切换开销：$s\cdot(|S|-1)$。只开一组时为 $0$；每多开一组，多扣一次 $s$。

$U=$ 亲和收益 $-$ 激活开销 $-$ 切换开销。只保留 $U\ge 0$ 的方案。

输入描述

第一行五个整数 $n,m,k,q,s$。

第二行 $n$ 个整数 $w_1,w_2,\ldots,w_n$。

第三行 $m$ 个整数 $c_1,c_2,\ldots,c_m$。

第四行 $m$ 个整数 $a_1,a_2,\ldots,a_m$。

接下来 $n$ 行，第 $i$ 行 $m$ 个整数 $p_{i,1},p_{i,2},\ldots,p_{i,m}$。

约束

$1 \le n \le 40$

$1 \le m \le 8$

$1 \le k \le m$

$1 \le q \le n$

$0 \le s \le 10^4$

$1 \le w_i \le 100$

$1 \le c_j \le 4000$

$0 \le a_j \le 10^4$

$0 \le p_{i,j} \le 1000$

输出描述

输出一个整数，表示最大净收益。没有可用方案时输出 $-1$。

样例1

输入

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

输出

9

说明

只开 $1$ 组时四段负载和为 $11$，三组容量分别为 $5,9,6$，均不够。

$[1]$ 给组 $1$、$[2,4]$ 给组 $2$：负载 $2\le 5$、$9\le 9$，亲和 $8+9+8+2=27$，激活 $3+10=13$，切换 $5$，$U=9$。

$[1,2]$ 给组 $1$、$[3,4]$ 给组 $3$：负载 $5\le 5$、$6\le 6$，亲和 $8+3+2+7=20$，激活 $3+4=7$，切换 $5$，$U=8$。

$[1,3]$ 给组 $2$、$[4]$ 给组 $3$：负载 $7\le 9$、$4\le 6$，亲和 $1+9+8+7=25$，激活 $10+4=14$，切换 $5$，$U=6$。

其余两段划分的净收益都不超过 $9$。

样例2

输入

5 2 2 2 3
1 1 1 1 1
3 3
2 2
5 0
5 0
0 5
5 0
5 0

输出

8

说明

$[1,2]$ 给组 $1$、$[3,5]$ 给组 $2$：负载 $2\le 3$、$3\le 3$，亲和 $5+5+5+0+0=15$，激活 $2+2=4$，切换 $3$，$U=8$。

$[1,3]$ 给组 $2$、$[4,5]$ 给组 $1$：亲和 $0+0+5+5+5=15$，激活 $4$，切换 $3$，$U=8$。

第 $3$ 段不能单独成会话（长度 $1<2$）。组 $1$ 也不能在组 $2$ 两侧各开一次会话。