Background

William carried Xenoilius 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 Xenoilius to let the blade breathe.

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

Xenoilius immediately emitted a soft glow.

"— Adjustment begins."

Problem Description

Specifically, the holy sword Xenoilius consists of $n$ talismans, and each talisman has a weight $a_i$. William 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, William has some restrictions when adjusting them. Each restriction is in the form $(i,j,x,y)$, meaning that William 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, Ctholly wants to know what the minimum fatigue value is after William 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 William.

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