3900: 张老师的战力强化
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
张老师最近跟着王老师和石老师一起在玩一个游戏《o神》！
然而由于张老师开始的比较晚，所以他的角色战斗力并不高，只有 $x$
于是为了快速提升战斗力，张老师决定找王老师和石老师购买一些强化道具
然而王老师和石老师两个人手里的强化道具种类并不相同
- 王老师手里有 $n$ 种强化道具，第 $i$ 种强化道具可以让张老师的战斗力 $+a_i$
- 石老师手里有 $m$ 种强化道具，第 $i$ 种强化道具可以让张老师的战斗力 $* b_i$
但是张老师并不想在游戏里花太多钱，于是他决定从王老师和石老师手里一共购买 $k$ 种道具
现在张老师想知道，他的战斗力最大可以达到多少？
由于答案可能很大，请你将答案对 $998244353$ 取模
P.S. 每种强化道具只有一个
然而由于张老师开始的比较晚，所以他的角色战斗力并不高，只有 $x$
于是为了快速提升战斗力，张老师决定找王老师和石老师购买一些强化道具
然而王老师和石老师两个人手里的强化道具种类并不相同
- 王老师手里有 $n$ 种强化道具，第 $i$ 种强化道具可以让张老师的战斗力 $+a_i$
- 石老师手里有 $m$ 种强化道具，第 $i$ 种强化道具可以让张老师的战斗力 $* b_i$
但是张老师并不想在游戏里花太多钱，于是他决定从王老师和石老师手里一共购买 $k$ 种道具
现在张老师想知道，他的战斗力最大可以达到多少？
由于答案可能很大，请你将答案对 $998244353$ 取模
P.S. 每种强化道具只有一个
输入
输入第一行四个整数，$x,n,m,k$，含义如题
输入第二行包含 $n$ 个整数，第 $i$ 个整数为 $a_i$，分别表示王老师的每种强化道具
输入第三行包含 $m$ 个整数，第 $i$ 个整数为 $b_i$，分别表示石老师的每种强化道具
输入第二行包含 $n$ 个整数，第 $i$ 个整数为 $a_i$，分别表示王老师的每种强化道具
输入第三行包含 $m$ 个整数，第 $i$ 个整数为 $b_i$，分别表示石老师的每种强化道具
| 测试点编号 | $n,m\leq$ | $a_i,b_i,x\leq$ | 特殊性质 |
| :---: | :---: | :---: | :---: |
| $1$ | $3$ | $5$ | 无 |
| $2\sim 4$ | $10$ | $5$ | 无 |
| $5\sim 6$ | $10^5$ | $10^5$ | 答案不超过 $1e18$ |
| $7 \sim 10$ | $10^5$ | $10^5$ | 无 |
对于 $100\%$ 的数据：$1\leq n,m\leq 10^5,1\leq a_i,b_i,x\leq 10^5,1\leq k\leq n+m$。
| :---: | :---: | :---: | :---: |
| $1$ | $3$ | $5$ | 无 |
| $2\sim 4$ | $10$ | $5$ | 无 |
| $5\sim 6$ | $10^5$ | $10^5$ | 答案不超过 $1e18$ |
| $7 \sim 10$ | $10^5$ | $10^5$ | 无 |
对于 $100\%$ 的数据：$1\leq n,m\leq 10^5,1\leq a_i,b_i,x\leq 10^5,1\leq k\leq n+m$。
输出
输出一个整数，表示张老师最终可以达到的最大战斗力，并将答案对 $998244353$ 取模
样例输入 复制
2 2 2 1
4 1
2 2样例输出 复制
6提示
样例解释1
张老师选择购买王老师的一件道具，战斗力 $+4$ 变成 $2+4=6$ 最大
样例解释2
张老师选择购买王老师的 $+4$ 和石老师的两个 $* 3$ 达成最大值 $(4+2) * 3 * 3=54$
张老师选择购买王老师的一件道具，战斗力 $+4$ 变成 $2+4=6$ 最大
张老师选择购买王老师的 $+4$ 和石老师的两个 $* 3$ 达成最大值 $(4+2) * 3 * 3=54$