Problem Background

William has taken out the Ceniolis from the warehouse.

On the outskirts of the 68th floating island, atop a slightly elevated hill.

The wind is calm, the air is clear, the starlight is gentle, and the conditions are perfect for a night.

He lifts the cloth covering Ceniolis, allowing the blade to breathe.

William infuses a bit of magic. It slightly pains his temples, but this level is manageable.

Ceniolis immediately emits a soft glow.

「——Adjustment begins.」

Problem Description

Specifically, the holy sword Ceniolis consists of $n$ talismans, each with a weight value $a_i$. William will perform $k$ adjustments, each adjusting one talisman and accumulating fatigue equal to the talisman's weight.

However, due to some strange connection between the talismans, there are certain restrictions on William's adjustments. These restrictions are in the form of $(i,j,x,y)$, indicating that William must adjust one of the first $x$ talismans during the $i$-th adjustment or one of the last $y$ talismans during the $j$-th adjustment, otherwise the sword will collapse.

Now, Chtholly wants to know the minimum fatigue value William will accumulate after adjusting all the talismans.

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 following $q$ lines each contain four positive integers $i, j, x, y$.

Output Format

A single number representing the minimum fatigue value of William.

Sample Input and Output

Sample Input #1

3 2 1
2 1 3
1 2 2 2

Sample Output #1

2

Sample Input #2

3 2 1
2 1 3
1 2 1 1

Sample Output #2

3

Sample Input #3

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

Sample Output #3

4

Notes

Sample Explanation:

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

For the second sample, the first adjustment selects $a_1$, and the second adjustment selects $a_2$ to meet the restrictions with the minimum value.

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

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

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

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

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

见题面 Input 部分

见题面 Output 部分