시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Дед Афанасий решил подлатать забор вокруг своего деревенского участка. В прошлом году он как раз строил сарай, так что доски для ремонта у него остались.

Забор состоит из $n$ сегментов, каждый из которых представляет собой доску высотой $a_i$. У деда есть тележка, на которой лежит стопка из $m$ досок, про каждую из которых известна ее длина $b_i$.

Дед Афанасий идет вдоль забора и катит перед собой тележку с досками. Если он хочет увеличить высоту текущего сегмента, он может взять доску с тележки и прибить ее сверху. Тогда новая высота сегмента будет равна сумме изначальной высоты сегмента и длины прибитой доски. Дед не хочет прибивать больше одной доски к каждому сегменту забора, чтобы сохранить его прочность. 

Собираясь увеличить высоту сегмента забора, Афанасий поступает следующим образом. Он либо использует для увеличения сегмента верхнюю доску с тележки, либо выкидывает одну или несколько верхних досок с тележки и использует следующую доску. Силы у Афанасия уже не те, поэтому он никогда не возвращается назад вдоль забора и никогда не подбирает выкинутые ранее доски. 

Перед началом работы дед задумался, какую максимальную высоту может иметь забор после починки. Высотой забора Афанасий считает высоту самого низкого сегмента забора.

Помогите деду Афанасию узнать, какую максимальную высоту забора он сможет получить.

입력

В первой строке входного файла находится целое число $n$ --- количество сегментов в заборе ($1 \le n \le 10^5$). Во второй строке содержатся $n$ целых чисел $a_1, a_2, \ldots, a_n$ --- высоты сегментов забора, перечисленные в том порядке, в котором мимо них пройдет дед Афанасий ($1 \le a_i \le 10^8$).

В третьей строке находится целое число $m$ --- количество досок на тележке ($1 \le m \le 10^5$). В четвертой строке содержатся $m$ целых чисел $b_1, b_2, \ldots, b_m$ --- длины досок на тележке, начиная с верхней ($1 \le b_i \le 10^8$).

출력

В первую строку выходного файла выведите два целых числа $h$ и $k$ --- максимальную возможную высоту забора и количество досок, которые деду следует использовать при починке. В следующих $k$ строках выведите по два целых числа $x_i$ и $y_i$, которые означают, что к $x_i$-му сегменту забора деду следует прибить доску с номером $y_i$.

Если существует несколько способов починить забор требуемым образом, выведите любой из них.

예제 입력 1

3
10 5 10
1
5

예제 출력 1

10 1
2 1

예제 입력 2

6
2 5 4 1 7 5
7
2 3 1 3 2 4 6

예제 출력 2

5 3
1 2
3 4
4 7