题目描述
住在家里的XJC十分无聊,便开始在家中”掘地三尺“。在从30层挖掘到地下1000米后,XJC发现了远古先民的神秘遗物——七龙珠。嘎嘎嘎嘎嘎嘎嘎。
根据古老的典籍记述,XJC找到了 n 个零件,他要用这些零件拼成七颗龙珠,从而召唤神龙。
每一个零件可以表示为一个二元组 (ai,bi),其中 ai 是一个 1∼7 之间的整数,表示这个零件可以作为第几颗龙珠的一部分,bi 是一个 0∼109 之间的整数,表示这个零件的”能量值“。
XJC可以用一些零件合成一颗龙珠,龙珠的能量值就是组成它的所有零件的能量值之和。值得注意的一点是,XJC使用了辛苦钻研九九八十一年的冶炼技术,龙珠之间的区别只有能量值不同,与组成部分无关。举个例子,对于零件集合{(1,1),(1,2),(1,3),(1,4)} ,XJC可以选择用{(1,2),(1,3)} 这两个零件合成第一颗龙珠,也可以选择用{(1,1),(1,4)} 合成第一颗龙珠。因为合成的龙珠能量值都是 5 ,这两颗龙珠没有区别。
XJC希望合成七颗龙珠以便召唤神龙。经过七七四十九天的钻研,XJC终于从某hub上找到了神龙能力的计算公式:
f(a,b,c,d,e,f,g)=A×a+B×b+C×c+D×d+E×e+F×f+G×g,其中 a,b,c,d,e,f,g 分别表示第 1,2,3,4,5,6,7 颗龙珠的能量值,A,B,C,D,E,F,G 是某个给定的玄学常数。
在合成龙珠召唤神龙之前,XJC思考了一下他的人生目标。为了召唤神龙,找到npy,吊打yql,AKIOI,解决NP完全问题,XJC需要召唤能力恰好第 K 大的神龙。值得注意的一点是,召唤出的神龙和使用的龙珠这个七元有序组有关。举个例子,当 A=B=C=D=E=F=G=1 时,(1,2,3,4,5,6,7) 和 (7,6,5,4,3,2,1) 召唤出的神龙是不同的。
迫不及待的XJC开始了冶炼,但是他发现能量值过高的龙珠十分不稳定,容易爆炸。经过三七二十一次试验后他发现这个阈值是 M ,只有能量值小于等于 M 的龙珠才能安全地取出冶炼炉用来召唤神龙。
XJC找到了你,请帮他计算他召唤出的神龙的能力,你经不住XJC女装照的交换诱惑,决定帮他解决。
注意:我们可以不用任何零件凭空造出一个能量值是 0 的龙珠。
输入格式
第一行两个数 M,K 表示龙珠的稳定阈值和XJC要第几大的神龙。
第二行有 7 个整数,表示XJC测定的常数 A,B,C,D,E,F,G。
第三行到第九行,第 i 行的开头有一个数 xi ,表示XJC收集到 xi 个 a=i−2 的零件。
然后是 xi 个整数,表示这些零件的能量值(即 b 属性)。
输出格式
一行一个数,表示能力第 K 大的神龙的能力。
特别地,能召唤出的神龙条数不足 K ,输出 Stop dreaming XJC!
。
输入样例1
输出样例1
解释
请注意,只有≤M的龙珠才能被合成,不同的方案合成同样大小的龙珠在此处被看做是一样的。
输入样例2
输出样例2
解释
输入样例3
输出样例3
数据规模与约定
测试点编号 |
数据范围 |
1,2 |
M≤104,xi≤2,K≤105 |
3,4,5 |
M≤104,xi≤104,K=1 |
5,6,7,8,9,10 |
M≤104,xi≤104,K≤100 |
11,12,13,14,15,16 |
M≤104,xi≤104,K≤105 |
17,18,19,20 |
M≤105,xi≤104,K≤105 |
对于 100% 的数据,有 ∣A∣,∣B∣,∣C∣,∣D∣,∣E∣,∣F∣,∣G∣≤109,0≤b属性≤M。