解题思路

本题要求在总法力值不超过 M 的前提下，使得到的魔法强度之和最大。约束包括：课程必须按顺序学习（只能学前缀），每门课必须在某一层完整学习，楼层会同时放大收益与消耗，并且只在上行切换楼层时需要额外的法力消耗（等于楼层差），下行或不变不额外消耗。

核心做法是动态规划（DP），状态带上“已学到第几门课”“当前所处楼层”“已花费法力”。 设楼层从 1..m 编号、课程从 1..n。令：

• gain(i, j) = power[i] * bonus[j]：第 i 门课在第 j 层的强度增益；
• cost(i, j) = mana[i] * bonus[j]：第 i 门课在第 j 层的法力消耗；
• 从上一门所在楼层 p 到当前楼层 j 的切换代价为 max(0, j - p)（只上行收费）。

题目内容

多多进入了魔法学院学习，学院有 n 门不同的魔法课程，每门课程都有其独特的属性：

power[i]：学习这门课程能提升的魔法强度

mana[i]：学习这门课程需要消耗的法力值

学院的教学楼有m 层，每层有不同的环境加成系数 bonus[i]($1≤bonus[i]≤3$)。

多多总共有 M 点初始法力值。

特殊规则：

1.顺序学习：多多必须按顺序学习课程(必须先学课程 $1$，再学课程 $2$，以此类推)。

2.楼层绑定：每门课程只能在某一层完整学习，不能跨层。

3.强度加成：在第 j 层学习第 i 门课程时，获得的实际魔法强度为power[i] × bonus[j]。

4.法力消耗：在第 j 层学习第 i 门课程时，消耗的实际法力值为 mana[i] × bonus[j]。

5.切换代价：多多可以在不同楼层之间切换课程，第一次学习选择楼层没有切换代价，但每次切换可能会额外消耗楼层高度差的法力值。如果从低楼层切换到高楼层，比如从 $1$ 层切换到 $4$ 层,消耗 $3$ 点法力,如果从高楼层切换到低楼层,则不会消耗额外的法力

请求出在满足法力值限制(总法力消耗不超过 M )的条件下，多多能获得的最大魔法强度总和(无需学完所有课程)。

输入描述

第一行三个整数 n,m,M$(1≤n≤100,1≤m≤5,1≤M≤1000)$

第二行 n 个整数，表示 power[i]$(1≤power[i]≤100)$

第三行 n 个整数，表示 mana[i]$(1≤mana[i]≤100)$

第四行 m 个整数，表示 bonus[j]$(1≤bonus[j]≤3)$

输出描述

输出一个整数，表示能获得的最大魔法强度总和。如果无法完成任何课程(例如，第一门课程在任何一层学习的法力消耗都超过 M )，则输出 $0$ 。

补充说明

对于 $20$ %的数据：$n≤10,1≤m≤5,1≤M≤1000$

对下 $60$ % 的数据：$n≤30,1≤m≤5,1≤M≤1000$

对于 $100$ %的数据：$1≤n≤100,1≤m≤5, 1≤M≤1000$

样例1

输入

1 1 5
10
5
2

输出

0

说明

$1$ 门课程，$1$ 层楼，初始法力值 $5$ 课程强度 $10$，消耗 $5$ ，楼层加成 $2$ 实际消耗 $=5×2=10>5$ (无法学习)

样例2

输入

2 2 20
5 10
2 3
2 3

输出

45

说明

$2$ 门课程，$2$ 层楼，初始法力值 $[2,3]$

课程强度: $[5,10]$，消耗: $[2,3]$，楼层加成: $[2, 3]$

可能的方案:

都在 $1$ 层(加成 $2$ )：消耗 $=2×2+3×2=4+6=10$，强度 $=5×2+10×2=10+20=30$

都在 $2$ 层(加成 $3$)：消耗 $=2×3+3×3=6+9=15$，强度 $=5×3+10×3=15+30=45$

课程 $1$ 在 $1$ 层，课程 $2$ 在 $2$ 层：切换消耗 $=2-1=1$，总消耗 $=2×2+3×3+1=4+9+1=14$，强度 $=5×2+10×3 =10+30=40$

课程 $1$ 在 $2$ 层，课程 $2$ 在 $1$ 层：切换消耗 $=0$，总消耗 $=2×3+3×2=6+6=12$，强度 $=5×3+10×2=15+20=35$