← 返回题目列表

Codeforces · 620/D

D. GukiZ教授和两个阵列

中文机器翻译题面 查看原题

GukiZ 教授有两个整数数组,a 和 b。教授想让数组a sa 中的元素之和尽可能接近数组b sb 中的元素之和。所以他想要最小化值 v = |sa - sb|。

在一次操作中,教授可以交换数组 a 中的一些元素和数组 b 中的一些元素。例如,如果数组 a 是 [5, 1, 3, 2, 4],数组 b 是 [3, 3, 2],教授可以交换数组 a 中的元素 5 和数组 b 中的元素 2,得到新数组 a [2, 1, 3, 2, 4] 和新数组 b [3, 3, 5]。

教授不想进行两次以上的交换。找到最小值 v 以及不超过两次交换的某个序列,该序列将导致该值 v。教授逐一进行交换,每次新交换都与新数组 a 和 b 进行交换。

输入

第一行包含整数 n (1 ≤ n ≤ 2000) — 数组 a 中的元素数量。

第二行包含 n 个整数 ai (- 109 ≤ ai ≤ 109) — 数组 a 的元素。

第三行包含整数 m (1 ≤ m ≤ 2000) — 数组 b 中的元素数量。

第四行包含 m 个整数 bj (- 109 ≤ bj ≤ 109) — 数组 b 的元素。

输出

在第一行中打印最小值 v = |sa - sb|不超过两次交换即可获得。

第二行应包含交换次数 k (0 ≤ k ≤ 2)。

接下来的 k 行中的每一行都应包含两个整数 xp, yp (1 ≤ xp ≤ n, 1 ≤ yp ≤ m) — 第 p 个交换中数组 a 中元素的索引和数组 b 中元素的索引。

如果有多个最优解,则打印其中任意一个。按照教授进行交换的顺序打印交换内容。

示例

输入 #1

5
5 4 3 2 1
4
1 1 1 1

输出 #1

1
2
1 1
4 2

输入 #2

5
1 2 3 4 5
1
15

输出 #2

0
0

输入 #3

5
1 2 3 4 5
4
1 2 3 4

输出 #3

1
1
3 1