暂无测试数据。

Background

Description

篝喜欢咖啡。
篝了解到一共有 n 种罐装咖啡，其中第 i 种咖啡的拉环有 Ai 的几率出现“再来一罐”。这 n 种罐装咖啡顺时针排列成一个圆圈，若中奖，篝得到的不是第 i种咖啡，而是从 i 顺时针向后数的第 Bi 种咖啡。所有咖啡的数量都是无限的，当篝取走一罐咖啡后，将会有一罐新的同种类咖啡填充原来的位置，该咖啡的参数 Ai 和 Bi 都和原来的咖啡一样。
篝有着神奇的能力。在一罐咖啡没有中奖时，篝可以改变这个结果，使这罐咖啡变为中奖状态。但这会带来世界线的变动，因此篝每次使用能力之后所有的Bi 将增加 1。能力的使用是有限制的：篝最多只能使用 k 次能力。
篝只能购买其中一罐咖啡。篝想要喝到尽量多罐咖啡，请告诉篝她应该购买
一罐哪种咖啡，以及期望下她最多能喝到多少罐咖啡。

Format

Input

第一行两个整数 n,k，表示咖啡的种类数以及篝可以使用能力的次数。
第二行 n 个实数，第 i 个数表示 Ai。所有 Ai 最多精确到小数点后 2 位。
第三行 n 个整数，第 i 个数表示 Bi。

Output

输出两个整数 x,y，表示篝购买第 x 种咖啡最优，期望下能喝到 y 罐。数据保证最优答案与其余答案的实际差超过 1e-4。为了避免实数比较，请对998244353 取模后输出。

Sample 1

Input

3 0
0.5 0.25 0.6
0 0 0

Output

3 499122179

Sample 2

Input

4 3
0.2 0.1 0.7 0.6
1 2 3 1

Output

1 174706707

Limitation

本题有 5 个子任务。仅当你通过一个子任务的所有测试点时，才能得到该子任务的分数。
对于所有数据， 1≤n≤2000， 0≤k≤2000， 0≤Ai＜1， 0≤Bi＜n。

子任务    特殊限制              分值
1         n,k≤50               10
2    所有 Ai 只为 0 或 0.5      10
3         k 为 0                5
4      所有 Bi 都为 0           25
5       没有特殊限制            50

1s, 256000KiB for each test case.

Hint

关于取模意义下的分数：设答案化为最简分式后的形式为 a/b，其中 a 和 b互质。输出整数 x 使得 bx≡a mod 998244353 且 0≤x＜998244353。可以证明这样的整数 x 是唯一的。

Source

CDQZ TEST