28743번 - Защитный барьер 다국어

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

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