问题描述
国王阅兵式会持续 $n$ 天，每天都有一场飞机表演，第 $i$ 天的飞行表演需要 $P_i$ 个飞行员。由于每个飞行员都不愿意无偿的连续工作（哪怕连续工作 2 天 ， 因为他们实在太困了），这个国家出台了 $m$ 个休假办法，当某个飞行员当天工作后，如果支付他 $S_j$ 的酬劳，他会在上次工作 $T_j$ 天后重新回来工作 $(1\le j\le m)$。（多么好的制度）
如果飞行员在第 $r$ 天工作且此时 $T_j = 1$，那么他会就在 $r+1$ 天继续工作。
一开始有 $k$ 名飞行员，但当然还可以招募新的飞行员，但是，招募需要 $P$ 天的时间，并且招募来的每个飞行员需要支付 $Q$ 作为酬劳。(也就意味着到第 $P$ 天你才可能用到新招募来的飞行员)
现在国王把安排飞行表演的任务交给了你，你需要合理的安排这次飞行表演使得每天的飞行员都是充足的，并且让总费用最低。最后请输出总费用。
输入描述
第一行一个整数表示测试组数：$T(T\le 5)$
对于每组数据，第一行两个整数 $n (n\le 200)$，$k$ 表示阅兵式的天数和一开始的飞行员数量。
第二行 $n$ 个数，用空格分隔，表示每一天所需要的飞行员的数目。
第三行 3 个整数 $m(m \le 5),P, Q$， 具体意义参见题面。
接下来的 $m$ 行每行 2 个整数，即 $S_i, T_i$。
输入的所有数据均在区间 $[0 , 200]$ 内
输出描述
对每组数据输出一行表示答案 ， 即最小费用。
如果无解输出 `No solution`
注： 整个过程不会超出32位带符号整数
输入样例
1
5 10
1 3 5 10 6
1 3 5
2 2
输出样例
48
