AT_kupc2017_h Make a Potion

[problemUrl]: https://atcoder.jp/contests/kupc2017/tasks/kupc2017_h $ n $ 種類の液体を調合して $ 1 $ つのポーションを作ろうとしています。 $ i $ 種類目 $ (1\ \leq\ i\ \leq\ n) $ の液体は体積が $ v_i $ あります。 液体をそれぞれ体積 $ w_1 $, $ w_2 $, $ ... $, $ w_n $ 使うと、ポーションの効力は $ Σw_i\ \times\ h_i $ になります。 ただし、使う体積は整数でなければなりません。 さらに、$ m $ 個の条件があり、$ i $ 番目 $ (1\ \leq\ i\ \leq\ m) $ の条件は以下の通りです。 - $ a_i $ 種類目の液体を体積 $ x_i $ 以上使うなら、$ b_i $ 種類目の液体を体積 $ y_i $ 以上使わなければならない 条件を満たすように液体を使ったときのポーションの効力の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ m $ $ v_1 $ $ v_2 $ $ ... $ $ v_n $ $ h_1 $ $ h_2 $ $ ... $ $ h_n $ $ a_1 $ $ x_1 $ $ b_1 $ $ y_1 $ $ a_2 $ $ x_2 $ $ b_2 $ $ y_2 $ $ : $ $ a_m $ $ x_m $ $ b_m $ $ y_m $

ポーションの効力の最大値を標準出力に $ 1 $ 行で出力せよ。

### 制約 - 入力は全て整数である - $ 1\ \leq\ n\ \leq\ 1,000 $ - $ 1\ \leq\ m\ \leq\ 2,000 $ - $ 1\ \leq\ v_i\ \leq\ 10^6 $ $ (1\ \leq\ i\ \leq\ n) $ - $ -10^6\ \leq\ h_i\ \leq\ 10^6 $ $ (1\ \leq\ i\ \leq\ n) $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ n $ $ (1\ \leq\ i\ \leq\ m) $ - $ 0\ \leq\ x_i\ \leq\ v_{a_i} $ $ (1\ \leq\ i\ \leq\ m) $ - $ 0\ \leq\ y_i\ \leq\ v_{b_i} $ $ (1\ \leq\ i\ \leq\ m) $ - 同じ条件は複数回与えられない ### Sample Explanation 1 $ 1 $ 種類目の液体を体積 $ 800 $、$ 2 $ 種類目の液体を体積 $ 10 $ 使ったときの効力が最大です。 ### Sample Explanation 2 $ 1 $ 種類目の液体を少なくとも体積 $ 400 $ 使わなければなりません。 ### Sample Explanation 4 答えが $ 32 $ bit整数型に収まらない場合があります。