409678: GYM103678 A Бернард и IQ ПФО
Description
Одним весенним вечером Бернард сидел и размышлял о том, кто он такой. Внезапно он понял, что он персонаж задач школьной олимпиады «IQ ПФО».
Придя в себя спустя некоторое время, Бернард решил, что в таком случае не мешало бы украсить его комнату словами «IQ». Для этого он вырезал из бумаги $$$N$$$ палочек с длинами $$$L_i (1 \le i \le N)$$$, а также $$$M$$$ окружностей с радиусами $$$R_j (1 \le j \le M)$$$. Он решил составлять слова следующим образом: на букву «I» он потратит одну или несколько палочек, а на букву «Q» — одну окружность и одну или несколько палочек. Но не любые палочки будут гармонично смотреться с любыми окружностями. Некоторое время Бернард составлял различные комбинации и в итоге выяснил два правила идеального слова:
- Высота буквы «I» должна быть строго больше $$$R$$$ и строго меньше $$$3 \cdot R$$$, где $$$R$$$ — радиус окружности для буквы «Q».
- Длина «хвостика» буквы «Q» должна быть строго меньше радиуса окружности.
Когда Бернард использует несколько палочек для букв «I» или «Q», они соединяются последовательно, и длина получившейся палочки равна сумме длин вошедших в неё палочек.
Теперь Бернард задался вопросом, сколько существует различных вариантов идеального слова «IQ», которые можно составить из имеющихся палочек и окружностей. Два варианта считаются различными, если выполнено хотя бы одно из следующих условий:
- Отличаются высоты буквы «I».
- Отличаются длины «хвостиков» буквы «Q».
- Отличаются радиусы окружностей буквы «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», длина «хвостика»):
- (8, 5, 1)
- (10, 5, 1)
- (13, 5, 1)
- (6, 5, 3)
- (10, 5, 3)
- (11, 5, 3)
- (10, 5, 4)