using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); public static void Main() { Solve(); // Test(); } static void Test() { var r = new Random(); var count = 0; while (true) { var n = 4; var m = n; var x = r.Next(10); var map = new int[n][]; for (var i = 0; i < n; ++i) map[i] = new int[] { r.Next(10), r.Next(m) + 1 }; var k = 1; var c = new int[k]; for (var i = 0; i < k; ++i) c[i] = r.Next(n + 1); // 愚直解 var s1 = All(n, m, x, map, k, c); // 作成解 var s2 = Contest(n, m, x, map, k, c); if (s1 != s2) { WriteLine($"{n} {m} {x} {k}"); WriteLine(string.Join("\n", map.Select(m => string.Join(" ", m)))); WriteLine(string.Join(" ", c)); WriteLine(s1); WriteLine(s2); return; } ++count; if (count % 1000 == 0) WriteLine(count); } } static long All(int n, int m, int x, int[][] map, int k, int[] c) { var ans = 0L; Permutate(n, list => { var pts = 0L; foreach (var ci in c) { var gset = new HashSet(); for (var i = 0; i < ci; ++i) { pts += map[list[i]][0]; gset.Add(map[list[i]][1]); } pts += gset.Count * (long)x; } ans = Math.Max(ans, pts); }); return ans; } static void Permutate(int n, Action action) { var seed = new int[n]; for (var i = 0; i < n; ++i) seed[i] = i; var used = new bool[n]; var perm = new int[n]; Permutate(0, seed, perm, used, action); } static void Permutate(int pos, int[] seed, int[] perm, bool[] used, Action action) { if (pos == used.Length) action(perm); for (var i = 0; i < used.Length; ++i) { if (used[i]) continue; perm[pos] = seed[i]; used[i] = true; Permutate(pos + 1, seed, perm, used, action); used[i] = false; } } static void Solve() { var c = NList; var (n, m, x) = (c[0], c[1], c[2]); var map = NArr(n); var k = NN; c = NList; WriteLine(Contest(n, m, x, map, k, c)); } static long Contest(int n, int m, int x, int[][] map, int k, int[] c) { var counts = new int[n]; foreach (var ci in c) if (ci > 0) ++counts[ci - 1]; for (var i = counts.Length - 2; i >= 0; --i) counts[i] += counts[i + 1]; var glist = new List[m]; for (var i = 0; i < glist.Length; ++i) glist[i] = new List(); foreach (var p in map) glist[p[1] - 1].Add(new Pair(p[1] - 1, p[0])); for (var i = 0; i < glist.Length; ++i) glist[i].Sort((l, r) => r.Value.CompareTo(l.Value)); var tree = new AvlTree(); for (var g = 0; g < glist.Length; ++g) foreach (var v in glist[g]) tree.Insert(v); var tree2 = new PriorityQueue(); var ans = 0L; for (var i = 0; i < n; ++i) { if (tree.GetCount() > 0 && tree2.Count > 0) { var newpeek = tree.ElementAt(tree.GetCount() - 1); var newv = x + newpeek.Value; var oldv = tree2.Peek(); if (newv > oldv) { ans += (long)counts[i] * newv; tree.Delete(newpeek); for (var j = 1; j < glist[newpeek.Genre].Count; ++j) { tree.Delete(glist[newpeek.Genre][j]); tree2.Enqueue(glist[newpeek.Genre][j].Value, - glist[newpeek.Genre][j].Value); } } else { ans += (long)counts[i] * tree2.Dequeue(); } } else if (tree.GetCount() > 0) { var newpeek = tree.ElementAt(tree.GetCount() - 1); ans += (long)counts[i] * (x + newpeek.Value); tree.Delete(newpeek); for (var j = 1; j < glist[newpeek.Genre].Count; ++j) { tree.Delete(glist[newpeek.Genre][j]); tree2.Enqueue(glist[newpeek.Genre][j].Value, - glist[newpeek.Genre][j].Value); } } else { ans += (long)counts[i] * tree2.Dequeue(); } } return ans; } public class Pair : IComparable { public int Genre; public int Value; public Pair(int g, int v) { Genre = g; Value = v; } int IComparable.CompareTo(Pair other) { var d = Value.CompareTo(other.Value); if (d != 0) return d; return Genre.CompareTo(other.Genre); } } public class AvlTree where T: IComparable { private class Node where U: IComparable { public U Value; public Node Lc = null; public Node Rc = null; public int Height; public int Count; public int CCount; public Node(int height, U value) { Height = height; Count = 1; CCount = 1; Value = value; } } private Node root = null; static int GetHeight(Node t) { return t == null ? 0 : t.Height; } static int GetCount(Node t) { return t == null ? 0 : t.Count; } static int GetBalance(Node t) { return GetHeight(t.Lc) - GetHeight(t.Rc); } static void Recalc(Node t) { if (t == null) return; t.Height = 1 + Math.Max(GetHeight(t.Lc), GetHeight(t.Rc)); t.Count = t.CCount + GetCount(t.Lc) + GetCount(t.Rc); } static Node RotateLeft(Node t) { Node u = t.Rc; Node t2 = u.Lc; u.Lc = t; t.Rc = t2; Recalc(t); Recalc(u); return u; } static Node RotateRight(Node t) { Node u = t.Lc; Node t2 = u.Rc; u.Rc = t; t.Lc = t2; Recalc(t); Recalc(u); return u; } static Node RotateLR(Node t) { t.Lc = RotateLeft(t.Lc); return RotateRight(t); } static Node RotateRL(Node t) { t.Rc = RotateRight(t.Rc); return RotateLeft(t); } static Node BalanceLeft(Node t) { if (GetBalance(t) > 1) { if (GetBalance(t.Lc) < 0) t = RotateLR(t); else t = RotateRight(t); } Recalc(t); return t; } static Node BalanceRight(Node t) { if (GetBalance(t) < -1) { if (GetBalance(t.Rc) > 0) t = RotateRL(t); else t = RotateLeft(t); } Recalc(t); return t; } /// valueを挿入する public void Insert(T value) { root = Insert(root, value); } Node Insert(Node cur, T value) { if (cur == null) { return new Node(1, value); } var d = value.CompareTo(cur.Value); if (d < 0) { cur.Lc = Insert(cur.Lc, value); return BalanceLeft(cur); } else if (d > 0) { cur.Rc = Insert(cur.Rc, value); return BalanceRight(cur); } else { ++cur.CCount; Recalc(cur); return cur; } } /// valueを削除する 存在しない場合はなにもしない public void Delete(T value) { root = Delete(root, value); } Node Delete(Node cur, T value) { if (cur == null) return null; var d = value.CompareTo(cur.Value); if (d < 0) { cur.Lc = Delete(cur.Lc, value); return BalanceRight(cur); } else if (d > 0) { cur.Rc = Delete(cur.Rc, value); return BalanceLeft(cur); } else { --cur.CCount; if (cur.CCount == 0) { if (cur.Lc != null) { Node del = null; var max = DeleteMax(cur.Lc, ref del); cur.Lc = max; cur.Value = del.Value; cur.CCount = del.CCount; return BalanceRight(cur); } else { return cur.Rc; } } else { Recalc(cur); return cur; } } } Node DeleteMax(Node t, ref Node del) { if (t.Rc == null) { del = t; return t.Lc; } else { var max = DeleteMax(t.Rc, ref del); t.Rc = max; return BalanceLeft(t); } } /// 小さいほうからpos番目の要素を取得する public T ElementAt(int pos) { if (pos < 0 || pos >= GetCount(root)) return default; var t = ElementAt(root, pos); return t.Value; } /// 小さいほうからpos番目の要素を取得する public T ElementAt(int pos, T defaultValue) { if (pos < 0 || pos >= GetCount(root)) return defaultValue; return ElementAt(pos); } Node ElementAt(Node cur, int pos) { if (pos < GetCount(cur.Lc)) return ElementAt(cur.Lc, pos); if (pos < GetCount(cur.Lc) + cur.CCount) return cur; if (pos < cur.Count) return ElementAt(cur.Rc, pos - GetCount(cur.Lc) - cur.CCount); return null; } public void Debug() { if (root == null) return; Console.WriteLine($"root val:{root.Value}, CCount:{root.CCount}, Count:{root.Count}"); Debug(root.Value, root.Lc); Debug(root.Value, root.Rc); } void Debug(T pval, Node cur) { if (cur == null) return; Console.WriteLine($"{pval} -> val:{cur.Value}, CCount:{cur.CCount}, Count:{cur.Count}"); Debug(cur.Value, cur.Lc); Debug(cur.Value, cur.Rc); } /// value以上でもっとも小さい値とその場所を返却する public T LowerBound(T value, ref int index) { var cur = root; T ans = default; var add = 0; index = GetCount(root); while (cur != null) { if (value.CompareTo(cur.Value) <= 0) { ans = cur.Value; index = add + GetCount(cur.Lc); cur = cur.Lc; } else { add += GetCount(cur.Lc) + cur.CCount; cur = cur.Rc; } } return ans; } /// 要素の個数を求める public int GetCount() { return GetCount(root); } } }