Time limit: 1 seconds

Memory limit: 512 megabytes

One has to wander through all the outer worlds to reach the innermost shrine at the end. —Gitanjali, Poet, Rabindranath Tagore

题目描述

提莫正在峡谷里采蘑菇:

从左到右一共有$n$个蘑菇排成一行,第$i$个蘑菇的种类为$a_i$,提莫需要从左到右逐个采集这些蘑菇.

提莫有$2$种采集方式:

1. 亲自动手采集$1$个蘑菇,这需要消耗他$c_0$的时间.
2. 使用自动采蘑菇机器人,一共有$m$种不同机器人,它们都遵循着相似的工作原理: 第i种机器人可以识别最多i种不同蘑菇,且对于这i种蘑菇它可以收集无限多个. 如果机器人遇到了它没识别过的蘑菇并且它已经识别的蘑菇种类还没达到它的上限i,它就会识别这种蘑菇并且采集它. 但是如果此时它达到了识别上限$i$,它就不会采集这个新品种的蘑菇并立即停止工作. 如果所有蘑菇都被采集完了,机器人也会停止工作.

第$i$种机器人需要的工作时间为$c_i$.(从它开始干活到停止所需的时间,和采了多少蘑菇无关.)

提莫可以使用无限次不同种类的机器人,且每个机器人的识别库均可以不相同.

现在提莫想知道他最少需要多长时间能采集完所有的$n$个蘑菇,并且他还要你给出在最少时间内采集完成的方案数.

方案数可能很大,他只需要你告诉他对方案数取模$998244353$后的结果.

输入

输入一共$T$组.

每组第一行有两个整数$n(1\leq n\leq 10^6)$,$m(1\leq m\leq 30)$.分别代表蘑菇个数和机器人种类.

每组第二行共有$n$个整数$a_1,a_2,...,a_n(1\leq a_i\leq n)$,其中$a_i$代表第$i$个蘑菇的种类.

每组第三行$m+1$个整数:$c_0,c_1,...,c_m(1\leq c_i \leq 10^6)$.其中$c_0$代表手动采集需要的时间,$c_i$表示使用第$i$种机器人需要的时间.

保证总的蘑菇个数不超过$10^7$.

输出

每组输出一行用单个空格分隔开的$2$个整数代表采集完所有蘑菇需要的最短时间以及对应的方案数,方案数请对$998244353$取模后输出.

3
5 2
1 2 1 3 1
3 4 6

8 3
1 2 1 3 4 1 1 2
2 4 6 10

1 1
1
15 14

12 3
16 9
14 1

Postscript

For someone special: We used to be complete wholes in our original nature, and now 'love' is the name for our pursuit of wholeness, for our desire to be complete.