I Wanna 系列游戏以其轻松丰富（？）的游戏体验，吸引着全球无数游戏爱好者的目光——

小散正在玩一个 I Wanna 游戏，现在他即将面临一场极其困难的 Boss 战。
在这之前，小散将从 颗宝石中恰好选取 颗以尝试提升自身的实力值，实力值越高，战斗就会越轻松。每颗宝石上带有两个 “羁绊” 效果，第 颗宝石的 “羁绊” 效果分别用整数 来表示。所有宝石的 恰好组成一个长度为 的排列，所有宝石的 也恰好组成一个长度为 的排列。
随后，我们记录小散取出的宝石中每种 “羁绊” 效果的出现次数：
如果出现了 次，则小散可以从该 “羁绊” 效果中得到 的实力值；
如果出现了 次，则小散可以从该 “羁绊” 效果中得到 的实力值；
如果出现了 次，则小散可以从该 “羁绊” 效果中得到 的实力值。
小散最终获得的总实力值，等于所有 种“羁绊”效果（）所带来的实力值之和。
当然，他希望自己的总实力值获得尽可能大。你能帮帮他吗？

【名词解释】
长度为 的排列：由 这 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， 是一个长度为 的排列，而 和 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

第一行输入两个整数 ，表示宝石总数、必须选取的宝石数。
第二行输入三个整数 ，表示不同情况下实力值的提升。
此后  行，第  行输入两个整数 ，表示第  颗宝石上带有的 “羁绊” 效果。

输出一个整数，表示小散所能获得的实力值的最大值。

6 3
0 3 8
1 4
4 1
3 3
2 6
6 5
5 2

24

在这个样例中，最优的方案是取出第  颗宝石。编号为  的“羁绊”均出现了  次，最终可以获得  的实力值。可以证明没有办法获得超过  的实力值。

6 2
4 0 3
1 2
2 1
3 4
4 3
5 5
6 6

22

8 4
4096 3072 1024
1 2
3 4
5 6
6 5
2 3
4 1
7 7
8 8

23552

本题数据量较大，我们建议您选取较快的读入方式。