C. Прогулка

Время: 1 сек.
Память: 64 Мб

Когда человек не хочет что-то делать, у него найдётся 1000000 причин это не делать. Вот и сейчас, когда Сева с Женей зовут Кирилла гулять в парк, у него моментально появилась куча дел. Однако, после многочасовых переговоров (за время которых, к слову, можно было успеть прогуляться) Кирилл согласился, но с некоторыми оговорками. Во-первых, врач наказывал ему не подниматься слишком высоко над уровнем моря (что это за врач, и с чем связан такой совет, никто не знает). Во-вторых, он был согласен гулять только по квадратам (так как у них аура лучше, чем у любой другой фигуры). Женя и Сева растерялись и даже испугались, что не найдут подходящего для прогулки места, поэтому обратились к вам, чтобы узнать, сколько таких областей существует.

Опишем требования Кирилла более формально:

• Парк представляет из себя матрицу размеров n × m. Каждый участок матрицы описывается числом A_i,j — высота соответствующего участка.
• Кирилл согласится на прогулку только по подквадрату парка. (Подквадратом парка будем считать любую квадратную подматрицу матрицы A)
• Кирилл согласится гулять по выбранному подквадрату только при условии, что суммарная высота данного квадрата меньше S. (Суммарная высота подквадрата — это сумма элементов матрицы A на соответствующем подквадрате).

Формат ввода

В первой строке вводятся 3 целых числа через пробел n, m  — размеры парка, S — ограничение на подквадраты (1 ≤ n, m ≤ 30, 1 ≤ S ≤ 10⁹). В каждой из следующих n строк вводятся m чисел через пробел A_i,j (0 ≤ A_{i, j} ≤ 10⁷).

Формат вывода

В единственной строке выведите количество участков парка, по которым согласится гулять Кирилл.

Примеры

Ввод	Вывод
2 3 4 1 2 3 4 5 6	3
2 3 11 1 2 3 4 5 6	6