#127. 蘑菇! 提莫来采蘑菇啦!
蘑菇! 提莫来采蘑菇啦!
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
题目描述
提莫正在峡谷里采蘑菇:
从左到右一共有个蘑菇排成一行,第个蘑菇的种类为,提莫需要从左到右逐个采集这些蘑菇.
提莫有种采集方式:
- 亲自动手采集个蘑菇,这需要消耗他的时间.
- 使用自动采蘑菇机器人,一共有种不同机器人,它们都遵循着相似的工作原理: 第i种机器人可以识别最多i种不同蘑菇,且对于这i种蘑菇它可以收集无限多个. 如果机器人遇到了它没识别过的蘑菇并且它已经识别的蘑菇种类还没达到它的上限i,它就会识别这种蘑菇并且采集它. 但是如果此时它达到了识别上限,它就不会采集这个新品种的蘑菇并立即停止工作. 如果所有蘑菇都被采集完了,机器人也会停止工作.
第种机器人需要的工作时间为.(从它开始干活到停止所需的时间,和采了多少蘑菇无关.)
提莫可以使用无限次不同种类的机器人,且每个机器人的识别库均可以不相同.
现在提莫想知道他最少需要多长时间能采集完所有的个蘑菇,并且他还要你给出在最少时间内采集完成的方案数.
方案数可能很大,他只需要你告诉他对方案数取模后的结果.
输入
输入一共组.
每组第一行有两个整数,.分别代表蘑菇个数和机器人种类.
每组第二行共有个整数,其中代表第个蘑菇的种类.
每组第三行个整数:.其中代表手动采集需要的时间,表示使用第种机器人需要的时间.
保证总的蘑菇个数不超过.
输出
每组输出一行用单个空格分隔开的个整数代表采集完所有蘑菇需要的最短时间以及对应的方案数,方案数请对取模后输出.
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.
Related
In following contests: