#PU1276. USACO 2023 January Contest, Bronze — Problem 2. Air Cownditioning II

USACO 2023 January Contest, Bronze — Problem 2. Air Cownditioning II

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 NN cows (1≤N≤201 \leq N \leq 20) live in a barn that contains a sequence of stalls in a row, numbered 1…1001 \ldots 100. Cow ii occupies a range of these stalls, starting from stall sis_i and ending with stall tit_i. The ranges of stalls occupied by different cows are all disjoint from each-other. Cows have different cooling requirements. Cow ii must be cooled by an amount cic_i, meaning every stall occupied by cow ii must have its temperature reduced by at least cic_i units. The barn contains MM air conditioners, labeled 1…M1 \ldots M (1≤M≤101 \leq M \leq 10). The iith air conditioner costs mim_i units of money to operate (1≤mi≤10001 \leq m_i \leq 1000) and cools the range of stalls starting from stall aia_i and ending with stall bib_i. If running, the iith air conditioner reduces the temperature of all the stalls in this range by pip_i (1≤pi≤1061 \leq p_i \leq 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 NN and MM. The next NN lines describe cows. The iith of these lines contains sis_i, tit_i, and cic_i. The next MM lines describe air conditioners. The iith of these lines contains aia_i, bib_i, pip_i, and mim_i. For every input other than the sample, you can assume that M=10M = 10.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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
One possible solution that results in the least amount of money spent is to
select those that cool the intervals $[2, 9]$, $[1, 2]$, and $[6, 9]$, for a
cost of $3 + 2 + 5 = 10$.
Problem credits: Aryansh Shrivastava and Eric Hsu