珂...珂...珂朵莉给你出了一道送分题： 给你一个长为n的序列{vi}，和一个数a，你可以从里面选出最多m个数 一个合法的选择的分数定义为选中的这些数的和加上额外规则的加分： 有b个额外的规则，第i个规则即为： 对于这个序列的所有长为a的连续子区间，如果这个子区间中对应的给出的xi个位置都被选中了，则这次选择的分数加上yi（yi可能为负数，这种情况下分数仍然要加上y）

输入描述:

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

输出描述:

一行一个数表示最大可能得到的分数

备注:

对于100%的数据，0 600