Старый фермер оставил трем своим сыновьям наследство — прямоугольное кукурузное поле, разбитое на n × m клеточек. Про каждую клеточку известно, сколько тонн кукурузы на ней растет. Своих сыновей фермер любил неодинаково, поэтому завещал разделить свое наследство на три части c суммарным количеством кукурузы A, B и C тонн.
Поле должно быть разделено двумя прямыми линиями, которые параллельны одной из сторон поля, а также друг другу. Линии должны проходить исключительно между клетками поля. Каждая полученная в результате часть поля должна состоять хотя бы из одной клеточки.
Ваша задача — найти количество способов разделить поле описанным выше способом, то есть провести две линии, рассекающие поле на три части таким образом, чтобы на одной из получившихся частей росло A тонн кукурузы, на другой B, а на оставшейся C.
Выходные данные
Выведите ответ — количество способов разделить наследство так, чтобы на одной из получившихся частей росло A тонн кукурузы, на другой B, а на оставшейся C. Если не существует ни одного способа, выведите 0.
Примечание
Линии раздела могут быть как горизонтальными, так и вертикальными, но должны быть параллельны друг другу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 1 1
1 1 1
1 1 1
3 3 3
|
2
|
|
2
|
2 5
1 1 1 1 1
2 2 2 2 2
3 6 6
|
3
|
|
3
|
3 3
1 2 3
3 1 2
2 3 1
5 6 7
|
0
|