AT_abc325_f [ABC325F] Sensor Optimization Dilemma

[problemUrl]: https://atcoder.jp/contests/abc325/tasks/abc325_f キーエンスの工場長であるあなたは、ベルトコンベア上のいくつかの区間をセンサーによって監視したいと考えています。 あなたが監視したい区間は全部で $ N $ 個あり、$ i $ 個目の区間の長さは $ D_i $ メートルです。 センサーには $ 2 $ 種類の候補があり、それぞれのセンサーに関する情報は以下の通りです。 - センサー $ j\ (1\leq\ j\ \leq\ 2) $ : 長さ $ L_j $ メートルの区間を監視できる。 価格は $ 1 $ 個あたり $ C_j $ であり、全体で最大 $ K_j $ 個まで使用することができる。 $ 1 $ つの区間をいくつかの区間に分割して監視することもできます。 また、センサーが監視する区間が重なっていたり、監視したい区間の長さより余分に監視していたりしても問題はありません。 例えば、$ L_1=4,L_2=2 $ であるとき、センサー $ 1 $ を $ 1 $ つ使って長さ $ 3 $ メートルの区間を監視したり、センサー $ 1,2 $ を $ 1 $ つずつ使って長さ $ 5 $ メートルの区間を監視したりすることが可能です。 $ N $ 個の区画をすべて監視することが可能であるか判定し、可能ならば必要なセンサーの価格の総和の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ D_1 $ $ D_2 $ $ \dots $ $ D_N $ $ L_1 $ $ C_1 $ $ K_1 $ $ L_2 $ $ C_2 $ $ K_2 $

$ N $ 個の区画をすべて監視することが不可能ならば `-1` を、可能ならば必要なセンサーの価格の総和の最小値を出力せよ。

### 制約 - $ 1\leq\ N\ \leq\ 100 $ - $ 1\leq\ D_i,L_j\ \leq\ 10^5 $ - $ 1\leq\ C_j\ \leq\ 10^9 $ - $ 1\leq\ K_j\ \leq\ 10^3 $ - 入力は全て整数 ### Sample Explanation 1 以下のようにすることで、センサー $ 1 $ を $ 3 $ つ、センサー $ 2 $ を $ 4 $ つ使ってすべての区間を監視できます。 - センサー $ 1 $ を $ 1 $ つ使って $ 1 $ 個目の区間を監視する。 - センサー $ 1,2 $ を $ 1 $ つずつ使って $ 2 $ 個目の区間を監視する。 - センサー $ 1 $ を $ 1 $ つ、センサー $ 2 $ を $ 3 $ つ使って $ 3 $ 個目の区間を監視する。 このとき、必要なセンサーの価格の総和は $ 3\times\ 3\ +\ 2\times\ 4\ =\ 17 $ であり、これが最小です。 ### Sample Explanation 3 $ 1 $ つも使わない種類のセンサーがあっても構いません。