题目描述

强哥最近跟着强弟强妹一起在玩一个游戏《o神》！

然而由于强哥开始的比较晚，所以他的角色战斗力并不高，只有 $x$

于是为了快速提升战斗力，强哥决定找强弟和强妹购买一些强化道具

然而强弟和强妹两个人手里的强化道具种类并不相同

• 强弟手里有 $n$ 种强化道具，第 $i$ 种强化道具可以让强哥的战斗力 $+a_i$
• 强妹手里有 $m$ 种强化道具，第 $i$ 种强化道具可以让强哥的战斗力 $* b_i$

但是强哥并不想在游戏里花太多钱，于是他决定从强弟和强妹手里一共购买 $k$ 种道具

现在强哥想知道，他的战斗力最大可以达到多少？

由于答案可能很大，请你将答案对 $998244353$ 取模

P.S. 每种强化道具只有一个

输入格式（power.in）

输入第一行四个整数，$x,n,m,k$，含义如题

输入第二行包含 $n$ 个整数，第 $i$ 个整数为 $a_i$，分别表示强弟的每种强化道具

输入第三行包含 $m$ 个整数，第 $i$ 个整数为 $b_i$，分别表示强妹的每种强化道具

输出格式（power.out）

2 2 2 1
4 1
2 2

6

强哥选择购买强妹的一件道具，战斗力 $+4$ 变成 $2+4=6$ 最大

2 2 3 3
2 4
2 3 3

54

强哥选择购买强弟的 $+4$ 和强妹的两个 $* 3$ 达成最大值 $(4+2) * 3 * 3=54$

提示

对于 $100\%$ 的数据：$1\leq n,m\leq 10^5,1\leq a_i,b_i,x\leq 10^5,1\leq k\leq n+m$。