Рудольф собирается в гости к Бернарду, доехать до него он решил на метро. Билет можно купить в автомате, который принимает ровно две монеты, сумма которых не превышает \(k\).
У Рудольфа есть два кармана с монетами. В левом кармане лежат \(n\) монет номиналов \(b_1, b_2, \dots, b_n\). В правом кармане лежат \(m\) монет номиналов \(c_1, c_2, \dots, c_m\). Для оплаты он хочет выбрать ровно одну монету из левого кармана и ровно одну монету из правого кармана (суммарно две монеты).
Помогите Рудольфу узнать, сколько существует способов выбрать такие индексы \(f\) и \(s\), что \(b_f + c_s \le k\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество способов, которыми Рудольф может выбрать две монеты, доставая по одной из каждого кармана, чтобы сумма монет не превышала \(k\).
Примечание
Обратите внимание, в парах указаны индексы монет в массиве, а не их номиналы.
В первом наборе Рудольф может выбрать следующие пары монет: \([1, 1], [1, 2], [1, 4], [2, 1], [2, 2], [2, 4]\).
Во втором наборе Рудольф не может выбрать из двух карманов по одной монете ни одним способом, поскольку сумма любых двух элементов из первого и второго массивов будет превышать значение \(k=4\).
В третьем наборе Рудольф может выбрать: \([1, 1], [2, 1], [3, 1], [4, 1]\).
В четвертом наборе Рудольф может выбрать любую монету из левого кармана и любую монету из правого кармана.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 4 8
1 5 10 14
2 1 8 1
2 3 4
4 8
1 2 3
4 2 7
1 1 1 1
2 7
3 4 2000
1 1 1
1 1 1 1
|
6
0
4
12
|