题目描述

徐老师最近跟着王老师和石老师一起在玩一个游戏《o神》！然而由于徐老师开始的比较晚，所以他的角色战斗力并不高，只有 $x$ ，于是为了快速提升战斗力，徐老师决定找王老师和石老师购买一些强化道具然而王老师和石老师两个人手里的强化道具种类并不相同

• 王老师手里有 $n$ 种强化道具，第i种强化道具可以让徐老师的战斗力$+a_i$

• 石老师手里有 m 种强化道具，第i种强化道具可以让徐老师的战斗力$\times b_i$

但是徐老师并不想在游戏里花太多钱，于是他决定从王老师和石老师手里一共购买 $k$ 个道具

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

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

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

输入格式

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

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

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

输出格式

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