Minimizing Fatigue with Sword Amulets

Senio-illus Sword is composed of $n$ amulets with weights $a_i$. William will perform exactly $k$ adjustments; in each adjustment he picks one amulet and incurs fatigue equal to its weight. However, due to a strange link between the amulets, there are restrictions on the adjustments. Each restriction is given as a 4‐tuple $(i, j, x, y)$, which means that during the $i$–th adjustment he must choose an amulet among the first $x$ amulets (i.e. with index $\le x$) or during the $j$–th adjustment he must choose an amulet among the last $y$ amulets (i.e. with index $\ge n-y+1$); otherwise the sacred sword will collapse.

Note that each amulet can be adjusted more than once. Determine the minimum total fatigue incurred after all $k$ adjustments.

inputFormat

The first line contains three integers $n$, $k$, and $q$, where $n$ is the number of amulets, $k$ is the number of adjustments, and $q$ is the number of restrictions.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the weight of each amulet.

Each of the next $q$ lines contains four integers $i$, $j$, $x$, and $y$, describing a restriction as explained above.

outputFormat

Output a single integer --- the minimum total fatigue value after performing all $k$ adjustments while satisfying all restrictions. If no valid sequence of adjustments exists, output -1.

sample

3 3 1
1 2 3
1 3 2 1

3