Пауль наслаждается концертом симфонического оркестра. Секция струнных инструментов представляет собой клетчатый прямоугольник r × c. В каждой клетке находится скрипач, за исключением n клеток с альтистами. Паулю очень нравятся альты, поэтому он хочет сделать фотографию, на которой будет как минимум k альтистов. Пауль может сфотографировать некоторый прямоугольник со сторонами, параллельными осям координат. Посчитайте, сколько различных подходящих фотографий он может сделать.
Две фотографии считаются различными, если отличаются координаты соответствующих прямоугольников.
Выходные данные
Выведите единственно целое число — количество различных фотографий, на которых будут хотя бы k альтов.
Примечание
Будем использовать «*» для обозначения скрипачей и «#» для альтистов.
В первом примере оркестр выглядит следующим образом:
*#
**
Пауль может сделать фотографию, содержащую только альтиста, прямоугольник
1 × 2, содержащий весь столбец с альтистом,
2 × 1 строчку с альтистом или сфотографировать разом всю секцию струнных инструментов. Таким образом, возможны
4 фотографии.
Во втором примере оркестр выглядит следующим образом:
#*
*#
#*
Паулю подойдёт только фотография всего оркестра.
В третьем примере оркестр выглядит так же, как и во втором.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 1 1
1 2
|
4
|
|
2
|
3 2 3 3
1 1
3 1
2 2
|
1
|
|
3
|
3 2 3 2
1 1
3 1
2 2
|
4
|