P8465 "REOI-1" Adjusting the Holy Sword.

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."

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.**

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 one number, the minimum possible total fatigue value of William.

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