Sum of Maximums
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given $$$q$$$ pairs of integers $$$(l_1; r_1), (l_2; r_2), \ldots, (l_k; r_k)$$$, such that $$$1 \leq l_i \leq r_i \leq n$$$.

Let's say that $$$f(b)$$$ is equal to the $$$\sum_{i=1}^{q}{max(b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}))}$$$.

For $$$m$$$ arrays $$$a_1, a_2, \ldots, a_m$$$ of length $$$n$$$ you need to find largest $$$f(b)$$$ among all $$$b$$$ which are permutations of $$$a_i$$$.

Input

The first line of input contains two integers $$$n, m$$$ ($$$1 \leq n \leq 30, 1 \leq m \leq 1000$$$) — the number of elements in $$$a_i$$$ and the number of arrays for which you need to find the answer.

The second line of input contain one integer $$$q$$$ ($$$1 \leq q \leq 30$$$) — the number of given segments.

Next $$$q$$$ lines contain description of the given segments, $$$i$$$-th of them contain two integers $$$l_i, r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$).

Next $$$m$$$ lines contains descriptions of $$$a$$$, $$$i$$$-th of these lines contain $$$n$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i,n}$$$ ($$$0 \leq a_{i, j} \leq 10^9$$$).

Output

For each given array output one integer — the largest $$$f$$$ among all permutations of the given array.

Examples

Input
5 5
5
1 1
2 2
3 3
4 4
5 5
1 1 1 1 2
1 1 1 2 2
1 1 2 2 2
1 2 2 2 2
2 2 2 2 2
Output
6
7
8
9
10
Input
3 4
2
1 2
2 3
1 1 1
1 5 1
10 1 7
4 2 0
Output
2
10
20
8