Optimal Utilization

The device runs exactly one foreground app and one background app at the same time. Each app uses a positive amount of memory; IDs are distinct within the same type, while apps of different types may share an ID. Find all app ID pairs whose total memory does not exceed the capacity and is as large as possible, without missing different apps that use the same memory.

输入格式

The first line contains capacity n m, followed by n lines of foreground ID memory, then m lines of background ID memory. On this site 0≤n,m≤500, IDs are in −10^9..10^9 and distinct within each type, 1≤memory≤10^9, 0≤capacity≤2×10^9.

输出格式

Output a compact JSON two-dimensional array with the ID pairs in ascending lexicographic order; if there is no feasible pair, output [[]] as in the original problem.

样例 1

输入：

7 3 1
1 2
2 4
3 6
1 2

输出：

[[2,1]]

样例 2

输入：

4 2 2
2 2
1 2
9 2
8 2

输出：

[[1,8],[1,9],[2,8],[2,9]]

样例 3

输入：

16 2 2
2 7
3 14
2 10
3 14

输出：

[[]]

样例说明

The outputs are [[2,1]]; [[1,8],[1,9],[2,8],[2,9]]; and [[]]. In the second example the full Cartesian product must be kept; you cannot return just one of the optimal pairs.