珂学送分2
题号：NC14396
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

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

给你一个长为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