В школе, в которой учится Вася, идет подготовка к проведению выпускного. Одно из запланированных выступлений — бал, в котором примут участие пары состоящие из мальчиков и девочек.
Каждый класс должен представить на бал по две пары. В классе Васи \(a\) мальчиков и \(b\) девочек изъявили желание участвовать в мероприятии. Но не все мальчики и не все девочки готовы танцевать в паре.
Формально, вам известно \(k\) возможных пар, состоящих из одного мальчика и одной девочки. Вам нужно выбрать из этих пар две так, чтобы ни один человек не состоял больше чем в одной паре.
Например, если \(a=3\), \(b=4\), \(k=4\) и следующие пары готовы танцевать вместе \((1, 2)\), \((1, 3)\), \((2, 2)\), \((3, 4)\) (в каждой паре сначала идет номер мальчика, потом номер девочки), то возможны следующие комбинации из двух пар (ниже перечислены не все возможные варианты):
- \((1, 3)\) и \((2, 2)\);
- \((3, 4)\) и \((1, 3)\);
Но следующие комбинации не возможны:
- \((1, 3)\) и \((1, 2)\) — первый мальчик входит сразу в две пары;
- \((1, 2)\) и \((2, 2)\) — вторая девочка входит сразу в две пары;
Найдите количество способов выбрать две пары, походящие под условие выше. Два способа считаются различными, если состоят из разных пар.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите одно целое число — количество способов выбрать две пары, походящие под условие выше.
Примечание
В первом наборе входных данных следующие комбинации из двух пар подходят:
- \((1, 2)\) и \((3, 4)\);
- \((1, 3)\) и \((2, 2)\);
- \((1, 3)\) и \((3, 4)\);
- \((2, 2)\) и \((3, 4)\).
Во втором наборе входных данных есть всего одна пара.
В третьем наборе входных данных следующие комбинации из двух пар подходят:
- \((1, 1)\) и \((2, 2)\);
- \((1, 2)\) и \((2, 1)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 4 4
1 1 2 3
2 3 2 4
1 1 1
1
1
2 2 4
1 1 2 2
1 2 1 2
|
4
0
2
|