Задача G. Праздники ≡

Условие

На планете в звездной системе Альфа Кентавра неделя состоит из A дней, а год — из B дней. Годы нумеруются последовательными натуральными числами: 1, 2, 3, … Кроме того, годы с номерами C₁, C₂, …, C_N являются високосными и состоят из (B+1) дней. В году дни с номерами D₁, D₂, …, D_M являются праздничными. Если праздник попадает на (B+1)-й день года, то он отмечается только в високосные годы. Первый день первого года является первым днем недели.

Один из жителей планеты решил устроиться на новую работу. В соответствии с заключенным трудовым договором он будет числиться на данной работе в течение E дней, начиная с первого дня 1-го года. По договору он имеет право выбрать один день недели (с 1 по A), который будет для него выходным. Праздничные дни также считаются нерабочими. Житель хочет выбрать себе выходной день таким образом, чтобы за период действия договора у него было максимальное количество нерабочих дней.

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

Формат входного файла

В первой строке входного файла через пробел записаны числа A и B — количество дней в неделе и в невисокосном году соответственно (1≤ A ≤ 2500, 1≤ B ≤ 10000). Во второй строке записано число N — количество високосных лет, и в третьей — номера C₁, C₂, …, C_N високосных лет в возрастающем порядке (0 ≤ N ≤ 5000, 1 ≤ C₁ < C₂ < … < C_N ≤ 10⁷). В следующей строке число M — количество праздничных дней в году, и на новой строке — D₁, D₂, …, D_M в возрастающем порядке (1 ≤ D₁ < D₂ < … < D_M ≤ B+1). В последней строке записано число E (1≤ E ≤ 10⁹). Известно, что житель заключил контракт не более чем на 10⁷ лет.

Формат выходного файла

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

Примеры тестов

7 13
1
2
2
1 14
29

1 8

3 9
0

3
1 4 7
19

2 13