1979: [USACO 2023 January Contest Bronze] Problem 2. Air Cownditioning II

With the hottest recorded summer ever at Farmer John's farm, he needs a way to cool down his cows. Thus, he decides to invest in some air conditioners.

Farmer John's $N$ cows ($1\le N\le 20$) live in a barn that contains a sequence of stalls in a row, numbered $1\dots 100$. Cow $i$ occupies a range of these stalls, starting from stall $s_i$ and ending with stall $t_i$. The ranges of stalls occupied by different cows are all disjoint from each-other. Cows have different cooling requirements. Cow $i$ must be cooled by an amount $c_i$, meaning every stall occupied by cow $i$ must have its temperature reduced by at least $c_i$ units.

The barn contains $M$ air conditioners, labeled $1\dots M$ ($1\le M\le 10$). The $i$th air conditioner costs $m_i$ units of money to operate ($1\le m_i\le 1000$) and cools the range of stalls starting from stall $a_i$ and ending with stall $b_i$. If running, the $i$th air conditioner reduces the temperature of all the stalls in this range by $p_i$ ($1\le p_i\le {10}^6$). Ranges of stalls covered by air conditioners may potentially overlap.

Running a farm is no easy business, so FJ has a tight budget. Please determine the minimum amount of money he needs to spend to keep all of his cows comfortable. It is guaranteed that if FJ uses all of his conditioners, then all cows will be comfortable.

The first line of input contains $N$ and $M$.

The next $N$ lines describe cows. The $i$th of these lines contains $s_i$, $t_i$, and $c_i$.

The next $M$ lines describe air conditioners. The $i$th of these lines contains $a_i$, $b_i$, $p_i$, and $m_i$.

For every input other than the sample, you can assume that $M=10$.

2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5

10