题目描述

徐老师最近跟着王老师和石老师一起在玩一个游戏《o神》！

然而由于徐老师开始的比较晚，所以他的角色战斗力并不高，只有 $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$，分别表示石老师的每种强化道具

输出格式

输出一个整数，表示徐老师最终可以达到的最大战斗力，并将答案对 $998244353$ 取模

数据范围

测试点编号	$n,m\leq$	$a_i,b_i,x\leq$	特殊性质
$1$	$3$	$5$	无
$2\sim 4$	$10$
$5\sim 6$	$10^5$		答案不超过 $1e18$
$7 \sim 10$			无

对于 $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

2 2 2 1
4 1
2 2

样例输出1

6

样例解释1

徐老师选择购买王老师的一件道具，战斗力 $+4$ 变成 $2+4=6$ 最大

样例输入2

2 2 3 3
2 4
2 3 3

样例输出2

54

样例解释2

徐老师选择购买王老师的 $+4$ 和石老师的两个 $* 3$ 达成最大值 $(4+2) * 3 * 3=54$