409678: GYM103678 A Бернард и IQ ПФО

A. Бернард и IQ ПФОограничение по времени на тест4 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Одним весенним вечером Бернард сидел и размышлял о том, кто он такой. Внезапно он понял, что он персонаж задач школьной олимпиады «IQ ПФО».

Придя в себя спустя некоторое время, Бернард решил, что в таком случае не мешало бы украсить его комнату словами «IQ». Для этого он вырезал из бумаги $$$N$$$ палочек с длинами $$$L_i (1 \le i \le N)$$$, а также $$$M$$$ окружностей с радиусами $$$R_j (1 \le j \le M)$$$. Он решил составлять слова следующим образом: на букву «I» он потратит одну или несколько палочек, а на букву «Q» — одну окружность и одну или несколько палочек. Но не любые палочки будут гармонично смотреться с любыми окружностями. Некоторое время Бернард составлял различные комбинации и в итоге выяснил два правила идеального слова:

1. Высота буквы «I» должна быть строго больше $$$R$$$ и строго меньше $$$3 \cdot R$$$, где $$$R$$$ — радиус окружности для буквы «Q».
2. Длина «хвостика» буквы «Q» должна быть строго меньше радиуса окружности.

Когда Бернард использует несколько палочек для букв «I» или «Q», они соединяются последовательно, и длина получившейся палочки равна сумме длин вошедших в неё палочек.

Идеальное слово

Теперь Бернард задался вопросом, сколько существует различных вариантов идеального слова «IQ», которые можно составить из имеющихся палочек и окружностей. Два варианта считаются различными, если выполнено хотя бы одно из следующих условий:

1. Отличаются высоты буквы «I».
2. Отличаются длины «хвостиков» буквы «Q».
3. Отличаются радиусы окружностей буквы «Q».

Бернард просит вас помочь ему с этим вопросом.

Входные данные

Первая строка входных данных содержит два целых числа $$$N$$$ и $$$M$$$ $$$(1 \le N, M \le 100)$$$ — количество палочек и окружностей соответственно.

Вторая строка содержит $$$N$$$ целых чисел $$$L_i (1 \le L_i \le 3\cdot 10^3)$$$ — длины палочек.

Третья строка содержит $$$M$$$ целых чисел $$$R_i (1 \le R_i \le 10^3)$$$ — радиусы окружностей.

Выходные данные

Выведите одно целое число — количество различных вариантов идеальных слов «IQ», которые можно составить из имеющихся палочек и окружностей.

Система оценки

Группа	Доп. ограничения	Баллы	Требуемые подзадачи	Тип проверки
$$$1$$$	$$$N \le 2$$$	$$$5$$$	—	Полная
$$$2$$$	$$$N \le 10$$$	$$$15$$$	$$$1$$$	Полная
$$$3$$$	$$$L_i = 1$$$	$$$15$$$	$$$1$$$	Полная
$$$4$$$	$$$R_i \le 100$$$	$$$25$$$	$$$1-3$$$	Полная
$$$5$$$	—	$$$40$$$	$$$1-4$$$	Полная

ПримерыВходные данные

5 1
1 3 5 10 20
5

Выходные данные

7

Входные данные

4 2
1 3 10 20
2 30

Выходные данные

3

Примечание

В первом примере можно собрать следующие варианты (высота «I», радиус «Q», длина «хвостика»):

1. (8, 5, 1)
2. (10, 5, 1)
3. (13, 5, 1)
4. (6, 5, 3)
5. (10, 5, 3)
6. (11, 5, 3)
7. (10, 5, 4)