该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

为了即将到来的全国大赛，湘北篮球队的主力们正在全力训练。

樱木花道发现自己的“篮球战力”并不高，只有 $x$。 为了在比赛中压制对手，他决定去请教流川枫和三井寿。

• 流川枫手里有 $n$ 种特殊训练方案，第 $i$ 种方案可以让花道的战力提升 $+a_i$。
• 三井寿手里有 $m$ 种体能药剂，第 $i$ 种药剂可以让花道的战力乘上 $b_i$。

但是花道的钱有限，他最多只能在两人那里总共选择 $k$ 种强化方式。

花道当然想知道：自己的战力最高能到多少？

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

（每种强化方式只能选择一次）

输入格式

• 第一行四个整数，$x, n, m, k$。
• 第二行包含 $n$ 个整数，表示流川枫的强化数值 $a_1,a_2,\cdots,a_n$。
• 第三行包含 $m$ 个整数，表示三井寿的药剂倍率 $b_1,b_2,\cdots,b_m$。

输出格式

输出一个整数，表示花道最终能达到的最大战力，对 $998244353$ 取模。

数据范围

保证：$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

解释： 樱木选择了流川枫的一种强化方案 $+4$，战力变为 $2+4=6$，达到最大。

样例输入2

2 2 3 3
2 4
2 3 3

样例输出2

54

解释： 樱木选择了流川枫的 $+4$ 和三井的两个 $\times 3$ 药剂，结果是 $(2+4)\times 3 \times 3 = 54$。