Красивая команда
Contest: VK Cup 2018 - Квалификация 2
Difficulty rating: 1700
Tags: *special, combinatorics, math

Завтра у хоккейной команды, которой руководит Евгений, важный матч. Евгению нужно выбрать шесть игроков, которые выйдут на лед в стартовом составе: один вратарь, два защитника и три нападающих.

Так как это стартовый состав, Евгения больше волнует, насколько красива будет команда на льду, чем способности игроков. А именно, Евгений хочет выбрать такой стартовый состав, чтобы номера любых двух игроков из стартового состава отличались не более, чем в два раза. Например, игроки с номерами 13, 14, 10, 18, 15 и 20 устроят Евгения, а если, например, на лед выйдут игроки с номерами 8 и 17, то это не устроит Евгения.

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

Input format:
Первая строка содержит три целых числа g, d и f (1 ≤ g ≤ 1 000, 1 ≤ d ≤ 1 000, 1 ≤ f ≤ 1 000) — число вратарей, защитников и нападающих в команде Евгения.

Вторая строка содержит g целых чисел, каждое в пределах от 1 до 100 000 — номера вратарей.

Третья строка содержит d целых чисел, каждое в пределах от 1 до 100 000 — номера защитников.

Четвертая строка содержит f целых чисел, каждое в пределах от 1 до 100 000 — номера нападающих.

Гарантируется, что общее количество игроков не превосходит 1 000, т. е. g + d + f ≤ 1 000. Все g + d + f номеров игроков различны.

Output format:
Выведите одно целое число — количество возможных стартовых составов.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
В первом примере всего один вариант для выбора состава, который удовлетворяет описанным условиям, поэтому ответ 1.

Во втором примере подходят следующие игровые сочетания (в порядке вратарь-защитник-защитник-нападающий-нападающий-нападающий):

- 16 20 12 13 21 11
- 16 20 12 13 11 10
- 16 20 19 13 21 11
- 16 20 19 13 11 10
- 16 12 19 13 21 11
- 16 12 19 13 11 10

Таким образом, ответ на этот пример — 6.

Example input:
1 2 3
15
10 19
20 11 13

Example output:
1

Example input:
2 3 4
16 40
20 12 19
13 21 11 10

Example output:
6

Editorial:
Алгоритм решения заключается в следующем.
Пусть минимальный номер, который мы возьмем в команду, принадлежит одному из вратарей. Тогда переберём кому из вратарей принадлежит этот номер. Пусть это вратарь, который имеет на футболке номер minG. Тогда мы можем взять в состав вместе с ним двух защитников и трёх нападающих с номерами от minG + 1 до 2·minG. Количество подходящих защитников cntD определяем с помощью прохода по всем защитникам, а количество подходящих нападающих cntF определяем с помощью прохода по всем нападающим. Таким образом, мы можем взять двух защитников из cntD защитников, эта величина равна D = cntD * (cntD - 1) / 2, а также взять трёх нападающих, эта величина равна F = cntF * (cntF - 1) * (cntF - 2) / 6. Так как для каждой пары защитников из D нам подойдет любая тройка нападающих из F, то нужно к ответу прибавить D·F.
Пусть минимальный номер, который мы возьмем в команду, принадлежит одному из защитников. Тогда переберём кому из защитников принадлежит этот номер. Пусть это защитник, который имеет на футболке номер minD. Тогда мы можем взять в состав вместе с ним одного вратаря, ещё одного защитника и трёх нападающих с номерами от minD + 1 до 2·minD. Количество подходящих вратарей cntG, количество подходящих защитников cntD и количество подходящих нападающих cntF определяем с помощью проходов по соответствующим массивам. Таким образом, мы можем взять одного вратаря, эта величина G = cntG, взять ещё одного защитника из cntD защитников, эта величина равна D = cntD, а также взять трёх нападающих, эта величина равна F = cntF * (cntF - 1) * (cntF - 2) / 6. Так как для каждого вратаря из G подойдет любой защитник из D и любая тройка нападающих из F, то нужно к ответу прибавить G·D·F.
Пусть минимальный номер, который мы возьмем в команду, принадлежит одному из нападающих. Тогда переберём кому из нападающих принадлежит этот номер. Пусть это нападающий, который имеет на футболке номер minF. Тогда мы можем взять в состав вместе с ним одного вратаря, двух защитников и двух нападающих с номерами от minF + 1 до 2·minF. Количество подходящих вратарей cntG, количество подходящих защитников cntD и количество подходящих нападающих cntF определяем с помощью проходов по соответствующим массивам. Таким образом, мы можем взять одного вратаря, эта величина G = cntG, взять двух защитников из cntD защитников, эта величина равна D = cntD * (cntD - 1) / 2, а также взять двух нападающих, эта величина равна F = cntF * (cntF - 1) / 2. Так как для каждого вратаря из G подойдет любая пара защитников из D и любая пара нападающих из F, то нужно к ответу прибавить G·D·F.
Стоит отметить, что не нужно забывать про переполнение и выполнять все вычисления в 64-битном типе данных.