Задача C. Антон сводит старые счеты

Автор:А. Карабанов, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

На чердаке у бабушки Антон нашел пару старых счёт. Первые счёты изначально имели n1 спиц, на каждой из которых располагалось по m1 костяшек, вторые — соответственно n2 спиц по m2 костяшек. Время не пощадило вычислительные приспособления, и часть спиц и костяшек оказалось утрачено.

Антон хочет знать, возможно ли починить какие-нибудь счёты, воспользовавшись спицами и костяшками других счёт (все костяшки и спицы — одинаковые).

Во втором примере первые счёты имели 2 спицы по 2 костяшки на каждой, на первой спице осталась одна костяшка, вторая спица со всеми костяшками исчезла. Вторые счёты имели три спицы по три костяшки, на первой спице костяшек не осталось (но сама спица уцелела), на второй сохранилось две костяшки, на третьей — все три. Первые счёты можно починить, забрав одну спицу и три костяшки из вторых счёт.

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

Входной файл содержит целые числа n1 m1 n2 m2, за которыми следует n1 чисел pi — количество оставшихся костяшек на i−й спице первых счёт, затем n2 чисел qi — количество оставшихся костяшек на i−й спице первых счёт. Если спица отсутствует, вместо соответствующего количества указывается число 1.

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

Выходной файл должен содержать единственное целое число:

Ограничения

1 ≤ n1, n2, m1, m2 ≤ 2000; 1 ≤ pi ≤ m1; 1 ≤ qi ≤ m2.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 10 1 5
10
5
12
2
2 2 3 3
1
-1
0
2
3
1

0.028s 0.006s 15