#127. 蘑菇! 提莫来采蘑菇啦!

    ID: 127 Type: Default 1000ms 512MiB Tried: 8 Accepted: 3 Difficulty: 10 Uploaded By: Tags>福建师范大学第26届低年级程序设计竞赛

蘑菇! 提莫来采蘑菇啦!

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

题目描述

提莫正在峡谷里采蘑菇:

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

提莫有22种采集方式:

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

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

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

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

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

输入

输入一共TT组.

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

每组第二行共有nn个整数a1,a2,...,an(1ain)a_1,a_2,...,a_n(1\leq a_i\leq n),其中aia_i代表第ii个蘑菇的种类.

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

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

输出

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

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.