CF1146G Zoning Restrictions

You are planning to build housing on a street. There are $ n $ spots available on the street on which you can build a house. The spots are labeled from $ 1 $ to $ n $ from left to right. In each spot, you can build a house with an integer height between $ 0 $ and $ h $ . In each spot, if a house has height $ a $ , you can gain $ a^2 $ dollars from it. The city has $ m $ zoning restrictions though. The $ i $ -th restriction says that if the tallest house from spots $ l_i $ to $ r_i $ is strictly more than $ x_i $ , you must pay a fine of $ c_i $ . You would like to build houses to maximize your profit (sum of dollars gained minus fines). Determine the maximum profit possible.

The first line contains three integers $ n,h,m $ ( $ 1 \leq n,h,m \leq 50 $ ) — the number of spots, the maximum height, and the number of restrictions, respectively. Each of the next $ m $ lines contains four integers $ l_i, r_i, x_i, c_i $ ( $ 1 \leq l_i \leq r_i \leq n $ , $ 0 \leq x_i \leq h $ , $ 1 \leq c_i \leq 5\,000 $ ).

Print a single integer denoting the maximum profit you can make.

In the first example, it's optimal to build houses with heights $ [1, 3, 2] $ . We get a gain of $ 1^2+3^2+2^2 = 14 $ . We don't violate any restrictions, so there are no fees, so the total profit is $ 14 - 0 = 14 $ . In the second example, it's optimal to build houses with heights $ [10, 8, 8, 10] $ . We get a gain of $ 10^2+8^2+8^2+10^2 = 328 $ , and we violate the second restriction for a fee of $ 39 $ , thus the total profit is $ 328-39 = 289 $ . Note that even though there isn't a restriction on building $ 1 $ , we must still limit its height to be at most $ 10 $ .