Защитный барьер
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Малефисента практикуется в создании защитного барьера для Топких Болот. Процесс создания барьера состоит из произнесения $$$n$$$ заклинаний. Пусть $$$i$$$-е произнесённое заклинание имеет силу $$$s_i$$$. Тогда прочность барьера будет равна:

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

Где $$$1 \le l_i \le r_i \le n$$$ для любого $$$1 \le i \le q$$$.

Малефисента попробует построить барьер $$$m$$$ раз, причем в $$$i$$$-й раз она планирует произнести заклинания с силами $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$. Но она пока что не определилась с порядком произнесения заклинаний для каждой попытки. Помогите ей определить максимальную прочность барьера, которой она может добиться, в каждой из попыток.

Входные данные

В первой строке даны два целых числа $$$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$$$).

Выходные данные

Для каждой попытки создания барьера выведите максимальную возможную прочность барьера, которой может добиться Малефисента.

Примеры

Входные данные
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