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 p = r.Next(40) + 1; var q = r.Next(40) + 1; var map = new int[n][]; for (var i = 0; i < n; ++i) { map[i] = new int[] { r.Next(10) + 1, r.Next(10) + 1 }; } // 愚直解 var s1 = All(n, p, q, map); // 作成解 var s2 = Ticket(n, p, q, map); if (s1 != s2) { WriteLine($"{n} {p} {q}"); WriteLine(string.Join("\n", map.Select(m => string.Join(" ", m)))); WriteLine(s1); WriteLine(s2); return; } ++count; if (count % 1000 == 0) WriteLine(count); } } static long All(int n, int p, int q, int[][] map) { var bitmax = (int)Math.Pow(3, n); var ans = 0L; for (var b = 0; b < bitmax; ++b) { var x = 0L; var y = 0L; var v = 0L; var tmp = b; for (var i = 0; i < n; ++i) { if (tmp % 3 == 1) { x += map[i][0]; v += map[i][1]; } else if (tmp % 3 == 2) { y += map[i][0]; v += map[i][1]; } tmp /= 3; } if (x <= p && y <= q) ans = Math.Max(ans, v); } return ans; } static void Solve() { var c = NList; var (n, p, q) = (c[0], c[1], c[2]); var map = NArr(n); WriteLine(Ticket(n, p, q, map)); } static long Ticket(int n, int p, int q, int[][] map) { if (n == 1) { return map[0][0] <= p || map[0][0] <= q ? map[0][1] : 0; } var bitmax = (int)Math.Pow(3, n / 2); var list = new List<(long x, long y, long v)>(); for (var b = 0; b < bitmax; ++b) { var x = 0L; var y = 0L; var v = 0L; var tmp = b; for (var i = 0; i < n / 2; ++i) { if (tmp % 3 == 1) { x += map[i][0]; v += map[i][1]; } else if (tmp % 3 == 2) { y += map[i][0]; v += map[i][1]; } tmp /= 3; } list.Add((x, y, v)); // WriteLine($"first {b} {x} {y} {v}"); } list.Sort((l, r) => l.x.CompareTo(r.x)); var sq = (int)Math.Sqrt(list.Count); var dicsize = (list.Count + sq - 1) / sq; var dic = new List<(long x, long y, long v)>[dicsize]; var ylist = new List[dicsize]; var seglist = new SegmentTree[dicsize]; var minx = Enumerable.Repeat(long.MaxValue, dicsize).ToArray(); var maxx = new long[dicsize]; for (var i = 0; i < dic.Length; ++i) { dic[i] = new List<(long x, long y, long v)>(); } for (var i = 0; i < list.Count; ++i) { var idx = i / sq; dic[idx].Add(list[i]); minx[idx] = Math.Min(minx[idx], list[i].x); maxx[idx] = Math.Max(maxx[idx], list[i].x); } for (var i = 0; i < dic.Length; ++i) { var yset = new HashSet{ 0 }; foreach (var di in dic[i]) yset.Add(di.y); ylist[i] = new List(yset); ylist[i].Sort(); seglist[i] = new SegmentTree(yset.Count, new SegOp()); for (var j = 0; j < dic[i].Count; ++j) { var pos = LowerBound(0, dic[i][j].y, ylist[i]); seglist[i][pos] = Math.Max(seglist[i][pos], dic[i][j].v); } } var ans = 0L; bitmax = (int)Math.Pow(3, n - n / 2); for (var b = 0; b < bitmax; ++b) { var x = 0L; var y = 0L; var v = 0L; var tmp = b; for (var i = n / 2; i < n; ++i) { if (tmp % 3 == 1) { x += map[i][0]; v += map[i][1]; } else if (tmp % 3 == 2) { y += map[i][0]; v += map[i][1]; } tmp /= 3; } // WriteLine($"second {b} {x} {y} {v}"); for (var i = 0; i < dicsize; ++i) { // if (b + 1 == bitmax) WriteLine($"dic{i} max:{maxx[i]}, min:{minx[i]}"); if (x + maxx[i] <= p) { var pos = Math.Min(ylist[i].Count - 1, LowerBound(0, q - y, ylist[i])); ans = Math.Max(ans, v + seglist[i].Prod(0, pos + 1)); // if (b + 1 == bitmax) // { // WriteLine($"pos {q - y} in list {string.Join(" ", ylist[i])} = {pos}"); // for (var j = 0; j < ylist[i].Count; ++j) Write($"{seglist[i][j]} "); // WriteLine(); // } } else if (x + minx[i] <= p) { for (var j = 0; j < dic[i].Count; ++j) { if (x + dic[i][j].x <= p && y + dic[i][j].y <= q) ans = Math.Max(ans, v + dic[i][j].v); if (b + 1 == bitmax) WriteLine($"j: {j}, v={dic[i][j].v}"); } } } } return ans; } class SegOp : ISegmentTreeOperator { public long Identity => 0L; public long Operate(long x, long y) { return Math.Max(x, y); } } interface ISegmentTreeOperator { T Identity { get; } T Operate(T x, T y); } class SegmentTree { int size; int log; T[] d; ISegmentTreeOperator op; void Update(int k) { d[k] = op.Operate(d[2 * k], d[2 * k + 1]); } public SegmentTree(int n, ISegmentTreeOperator op) { this.op = op; size = 1; while (size < n) size <<= 1; log = CountRZero(size); d = new T[2 * size]; for (var i = 0; i < d.Length; ++i) d[i] = op.Identity; } public SegmentTree(T[] v, ISegmentTreeOperator op) { this.op = op; size = 1; while (size < v.Length) size <<= 1; log = CountRZero(size); d = new T[2 * size]; for (var i = 0; i < size; ++i) d[i] = op.Identity; for (var i = 0; i < v.Length; ++i) d[size + i] = v[i]; for (var i = size - 1; i >= 1; --i) Update(i); } int CountRZero(int n) { var ans = 0; while (n % 2 == 0) { ++ans; n >>= 1; } return ans; } public T this[int p] { get { return d[p + size]; } set { p += size; d[p] = value; for (var i = 1; i <= log; ++i) Update(p >> i); } } public T Prod(int l, int r) { var sml = op.Identity; var smr = op.Identity; l += size; r += size; while (l < r) { if ((l & 1) != 0) sml = op.Operate(sml, d[l++]); if ((r & 1) != 0) smr = op.Operate(d[--r], smr); l >>= 1; r >>= 1; } return op.Operate(sml, smr); } T AllProd() => d[1]; } static int LowerBound(int left, long min, IList list) { if (list[left] >= min) return left; var ng = left; var ok = list.Count; while (ok - ng > 1) { var center = (ng + ok) / 2; if (list[center] < min) ng = center; else ok = center; } return ok; } }