#P18252. Defeat the Enemies

Defeat the Enemies

Defeat the Enemies

你需要击败 nn 个敌人。第 ii 个敌人最初有 aia_i 点生命值和 bib_i 点护甲值。

每次攻击时,你可以选择一个整数伤害值 xx,其中 1≤x≤k1\le x\le k,对所有敌人造成 xx 点伤害,并支付 cxc_x 的费用。你可以进行任意多次攻击。

伤害优先由护甲承受。击破护甲的那次攻击,其多余伤害不会继续扣除生命值。 具体地,当一个敌人受到 yy 点伤害时:

  • 如果它当前的护甲值大于 00,将其护甲值减去 yy;
  • 否则,将其生命值减去 yy;
  • 当它的生命值小于或等于 00 时,该敌人被击败。

求击败所有敌人的最小总费用,以及达到这个最小费用的不同攻击策略数量。

一个策略是攻击伤害依次组成的整数序列 [x1,x2,…,xL][x_1,x_2,\ldots,x_L],其中 1≤xj≤k1\le x_j\le k。两个策略当且仅当对应序列不同才视为不同;因此攻击顺序也参与区分。

策略数量对 998244353998244353 取模。最小总费用不取模。

输入格式

第一行包含整数 TT,表示测试用例数。

每个测试用例:

  1. 第一行包含两个整数 n,mn,m,分别表示敌人数和生命值、护甲值的上界。
  2. 第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示初始生命值。
  3. 第三行包含 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n,表示初始护甲值。
  4. 第四行包含整数 kk,表示每次攻击的最大伤害。
  5. 第五行包含 kk 个整数 c1,c2,…,ckc_1,c_2,\ldots,c_k,其中 cxc_x 是一次造成 xx 点伤害的费用。

输出格式

对每个测试用例输出一行,包含两个整数:最小总费用、达到最小费用的策略数量对 998244353998244353 取模的结果。

数据范围

  • 1≤T≤10001\le T\le1000;
  • 1≤n≤5×1051\le n\le5\times10^5;
  • 1≤m≤1041\le m\le10^4;
  • 1≤ai,bi≤m1\le a_i,b_i\le m;
  • 1≤k≤1001\le k\le100;
  • 1≤cx≤1091\le c_x\le10^9。

同一个输入文件中,所有测试用例的 nn 之和不超过 5×1055\times10^5,mm 之和不超过 10410^4。

样例

4
5 5
3 5 2 1 2
3 1 3 2 3
3
2 3 4
3 2
2 2 2
2 2 2
3
2 3 3
7 6
5 3 4 6 6 3 4
4 6 4 2 3 5 5
4
2 4 6 7
10 100
38 49 79 66 49 89 21 55 13 23
67 56 26 39 56 16 84 50 92 82
11
6 6 7 8 9 9 9 9 9 9 9
9 1
6 4
18 18
99 44387