AT_tenka1_2016_final_d 右往左往

[problemUrl]: https://atcoder.jp/contests/tenka1-2016-final/tasks/tenka1_2016_final_d ハシモトくんは、 $ N $ 個のタスクを割り当てられています。 タスク $ i $ は、一つ目のオフィスで作業する場合は $ A_i $ の時間が、二つ目のオフィスで作業する場合は $ B_i $ の時間がかかります。 $ n $ 回目のオフィス間の移動には $ C\ \times\ (n\ -\ 1)\ +\ D $ の時間がかかります。 また、タスク間には依存関係が $ M $ 個あり、タスク $ X_i $ を終わらせた後でないとタスク $ Y_i $ に着手できません。 ハシモトくんが最適に行動し、全てのタスクを終わらせるまでの時間を最小化した場合、かかる時間はどの程度になるでしょうか？ なお、タスク処理開始・終了はどちらのオフィスであっても良いものとします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ C $ $ D $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_N $ $ B_N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ : $ X_M $ $ Y_M $

ハシモトくんが全てのタスクを終えるまでに必要な最短の時間を $ 1 $ 行に出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 20 $ - $ 0\ \leq\ M\ \leq\ N\ \times\ (N-1)\ / $ $ 2 $ - $ 0\ \leq\ C\ \leq\ 1000 $ - $ 0\ \leq\ D\ \leq\ 1000 $ - $ 0\ \leq\ A_i,\ B_i\ \leq\ 1000 $ - $ 1\ \leq\ X_i,\ Y_i\ \leq\ N $ - $ i\ \neq\ j $ ならば $ X_i\ \neq\ X_j $ または $ Y_i\ \neq\ Y_j $ - タスク間の依存関係に循環はない - $ N $, $ M $, $ C $, $ D $, $ A_i $, $ B_i $, $ X_i $, $ Y_i $ は整数である