Background

Willem carried Seniorious out of the warehouse.

On a slightly raised hill at the edge of Floating Island No. 68.

It was a night with steady wind, clear air, gentle starlight, and all conditions were suitable.

He lifted the cloth covering Seniorious to let the blade breathe.

Willem injected a little magic power. His temples hurt a bit, but this level was nothing serious.

Seniorious immediately emitted a soft glow.

"— Adjustment begins."

Problem Description

Specifically, the holy sword Seniorious consists of $n$ talismans, and each talisman has a weight $a_i$. Willem will perform $k$ adjustments. In each adjustment, he adjusts one talisman and gains a fatigue value equal to the talisman's weight.

However, due to some strange connection between the talismans, Willem has some restrictions when adjusting them. Each restriction is in the form $(i,j,x,y)$, meaning that Willem must either adjust one of the first $x$ talismans in the $i$-th adjustment or adjust one of the last $y$ talismans in the $j$-th adjustment, otherwise the holy sword will collapse.

Now, Chtholly wants to know what the minimum fatigue value is after Willem finishes all adjustments.

Note that each talisman can be adjusted more than once.

Input Format

The first line contains three positive integers $n, k, q$.

The next line contains $n$ positive integers $a_1, a_2, a_3...a_n$.

The next $q$ lines each contain $4$ positive integers $i, j, x, y$.

Output Format

Output one number, the minimum possible total fatigue value of Willem.

3 2 1
2 1 3
1 2 2 2 

2

3 2 1
2 1 3
1 2 1 1 

3

10 4 2
5 2 1 3 3 1 4 5 5 3 
4 3 1 7
2 4 5 5

4

Hint

Sample explanation:

For the first sample, choose $a_2$ in the first adjustment and choose $a_2$ in the second adjustment. It can be proven that this is the minimum value that satisfies the restrictions.

For the second sample, choosing $a_1$ in the first adjustment and choosing $a_2$ in the second adjustment is the minimum value to satisfy the restrictions.

Constraints:

For $24\%$ of the testdata: $1 \le n \le 20$, $1 \le k, q \le 14$.

For $56\%$ of the testdata: $1 \le n \le 100$, $1 \le k, q \le 60$.

For $80\%$ of the testdata: $1 \le n \le 10^5$, $1 \le k, q \le 10^3$.

For $100\%$ of the testdata: $1 \le n \le 10^5$, $1 \le k, q \le 10^4$, $1 \le a_i \le 10^5$.

For each restriction: $1 \le i, j \le k$, $1 \le x, y \le n$.

Translated by ChatGPT 5