사과 시장

여러 가게가 모인 시장을 관리하고 있다. 가게는 $n \times m$ 격자 모양으로 배치되어 있고, 모든 가게가 사과를 판다. 어느 가게에서든 사과 한 개의 값은 정확히 1 말레이시아 링깃이다.

손님 여러 명이 이 시장을 지나간다. 각 손님은 시장의 부분 직사각형 안에 있는 가게만 들르고, 쓸 수 있는 돈이 정해져 있다. 또한 가게마다 사과 재고가 다르고 한정되어 있으며, 손님과 손님 사이에 재고는 다시 채워지지 않는다. 각 가게가 각 손님에게 사과를 몇 개 팔지 마음대로 정할 수 있을 때, 벌 수 있는 돈의 최댓값을 구하라.

입력은 테스트 케이스 하나로 이루어진다. 프로그램은 서로 다른 입력으로 여러 번 실행될 수 있다. 첫째 줄에 세 정수 $n$, $m$, $k$가 공백으로 구분되어 주어진다. 시장은 $n$개의 행과 $m$개의 열로 이루어져 있고 ($1 \le n, m \le 50$), 손님은 $k$명이다 ($1 \le k \le 10^5$).

다음 $n$개의 줄에는 각각 $m$개의 정수 $a$ ($0 \le a \le 10^9$)가 주어진다. 이 행렬은 각 가게의 사과 재고를 행 우선 순서로 나타낸다. $a[r, c]$는 $r$번째 행, $c$번째 열에 있는 가게의 사과 개수이다. 행 번호는 $1$부터 $n$까지, 열 번호는 $1$부터 $m$까지이다. 왼쪽 위 모서리가 $a[1, 1]$이고 오른쪽 아래 모서리가 $a[n, m]$이다.

다음 $k$개의 줄에는 손님 한 명을 나타내는 다섯 정수 $t$, $b$ ($1 \le t \le b \le n$), $l$, $r$ ($1 \le l \le r \le m$), $x$ ($0 \le x \le 10^9$)가 주어진다. 이 손님은 $(t, l)$부터 $(b, r)$까지의 부분 직사각형 (경계 포함) 안에서만 사과를 산다. $t$는 위, $b$는 아래, $l$은 왼쪽, $r$은 오른쪽 경계이다. 이 손님이 쓸 수 있는 돈은 정확히 $x$ 말레이시아 링깃이다.

각 가게가 각 손님에게 사과를 몇 개 팔지 정해서 벌 수 있는 돈의 최댓값을 정수 하나로 출력한다.