Малефисента практикуется в создании защитного барьера для Топких Болот. Процесс создания барьера состоит из произнесения $$$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