보호 장벽

말레피센트는 토프키 볼로트 늪지를 지키는 보호 장벽을 만드는 연습을 하고 있다. 장벽을 만드는 과정은 $n$개의 주문을 외우는 것으로 이루어진다. $i$번째로 외운 주문의 세기를 $s_i$라고 하자. 그러면 장벽의 강도는 다음과 같다.

$\sum_{i=1}^{q} \max_{j=l_i}^{r_i} s_j$

여기서 모든 $1 \le i \le q$에 대해 $1 \le l_i \le r_i \le n$이다.

말레피센트는 장벽을 $m$번 만들어 보려고 한다. $i$번째 시도에서는 세기가 $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$인 주문을 외울 계획이다. 다만 시도마다 주문을 외우는 순서는 아직 정하지 않았다. 각 시도에서 말레피센트가 달성할 수 있는 장벽의 최대 강도를 구하라.

첫 줄에 두 정수 $n$과 $m$이 주어진다. $n$은 장벽 하나를 만드는 데 쓰는 주문의 수이고, $m$은 장벽을 만들어 보는 시도 횟수이다 ($1 \le n \le 30$, $1 \le m \le 1\,000$).

둘째 줄에 정수 $q$($1 \le q \le 30$)가 주어진다.

이어지는 $q$개의 줄에 정수 $l_i$와 $r_i$가 주어진다($1 \le l_i \le r_i \le n$).

이어지는 $m$개의 줄에 정수 $n$개씩 $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$이 주어진다($0 \le a_{i,j} \le 10^9$).

각 시도마다 말레피센트가 달성할 수 있는 장벽의 최대 강도를 한 줄에 하나씩 출력한다.