Защитный барьер

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

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