首页 > 试题广场 >

珂学送分2

[编程题]珂学送分2

珂...珂...珂朵莉给你出了一道送分题：

给你一个长为n的序列{vi}，和一个数a，你可以从里面选出最多m个数

一个合法的选择的分数定义为选中的这些数的和加上额外规则的加分：

有b个额外的规则，第i个规则即为：

对于这个序列的所有长为a的连续子区间，如果这个子区间中对应的给出的xi个位置都被选中了，则这次选择的分数加上yi（yi可能为负数，这种情况下分数仍然要加上y）


输入描述:
第一行四个数n,m,a,b
之后一行n个数表示序列v
之后表示b个规则
每个规则先输入两个数xi和yi
之后一行xi个数，分别表示这给定的xi个位置


输出描述:
一行一个数表示最大可能得到的分数
示例1

输入

5 3 3 1
2 3 3 3 3
2 233
1 3

输出

474

说明

示例2

输入

5 3 3 1
111 222 333 444 555
2 52
1 3

输出

1384

说明


备注:
对于100%的数据，0 <= n <= 100 , 0 <= m <= 50 ，0
<= a <= 16 , 0 <= b <= 100000， 所有出现的数的绝对值<=
600
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

状压dp
上传者：牛客301599号
难度：
0条回答 14浏览

热门推荐

通过挑战的用户

查看代码

相关试题

珂学送分2

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号