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$$$.
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$$$).
For each given array output one integer — the largest $$$f$$$ among all permutations of the given array.
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
6 7 8 9 10
3 4 2 1 2 2 3 1 1 1 1 5 1 10 1 7 4 2 0
2 10 20 8