AT_s8pc_5_f Lunch Menu

[problemUrl]: https://atcoder.jp/contests/s8pc-5/tasks/s8pc_5_f AtCoder カフェでは $ N $ 個の食事があり, 番号が $ 1 $ から $ N $ までつけられている. 食事 $ i\ (1\ \leq\ i\ \leq\ N) $ のおいしさは $ a_i $ である. square1001 君は, $ Q $ 日間 AtCoder カフェで食事をする. $ i\ (1\ \leq\ i\ \leq\ Q) $ 日目の食事では, 番号が $ l_i $ 以上 $ r_i $ 以下の食事の中から最もおいしさの値が大きいものを選ぶ. また, そのような食事がない場合は食事をせずに帰る. あなたは悪魔であり, 魔力で $ N $ 個中 $ M $ 個の食事をメニューからかき消して選べないようにすることができる. あなたの目的は square1001 君の選ぶ食事のおいしさの合計を最小化することである. square1001 君の選ぶ食事のおいしさの合計の最小値を求めなさい.

N/A

N/A

### 制約 - $ N $ は $ 1 $ 以上 $ 50 $ 以下の整数. - $ M $ は $ 0 $ 以上 $ N $ 以下の整数. - $ Q $ は $ 1 $ 以上 $ 50 $ 以下の整数. - $ a_i\ (1\ \leq\ i\ \leq\ N) $ は $ 1 $ 以上 $ 1\ 000\ 000\ 000 $ 以下の整数. - $ l_i,\ r_i $ は $ 1\ \leq\ l_i\ \leq\ r_i\ \leq\ N $ を満たす整数. ### 小課題 小課題 $ 1 $ \[$ 60 $ 点\] - $ N\ \leq\ 15 $. - $ Q\ =\ 1 $. 小課題 $ 2 $ \[$ 60 $ 点\] - $ N\ \leq\ 15 $. 小課題 $ 3 $ \[$ 250 $ 点\] - すべての $ i\ (1\ \leq\ i\ \leq\ N) $ に対して, $ a_i\ =\ 1 $. 小課題 $ 4 $ \[$ 630 $ 点\] - 追加の制約はない. ### Sample Explanation 1 もしあなたが番号 $ 2 $, $ 3 $ の食事を消すと, それぞれの日の美味しさの最大値は $ 4 $, $ 3 $, $ 8 $, $ 4 $, $ 8 $ となり, 合計が $ 27 $ となる.