D - 右往左往 /

実行時間制限: 5 sec / メモリ制限: 256 MB

配点 : 700

問題文

ハシモトくんは、 N 個のタスクを割り当てられています。

タスク i は、一つ目のオフィスで作業する場合は A_i の時間が、二つ目のオフィスで作業する場合は B_i の時間がかかります。

n 回目のオフィス間の移動には C \times (n - 1) + D の時間がかかります。

また、タスク間には依存関係が M 個あり、タスク X_i を終わらせた後でないとタスク Y_i に着手できません。

ハシモトくんが最適に行動し、全てのタスクを終わらせるまでの時間を最小化した場合、かかる時間はどの程度になるでしょうか?

なお、タスク処理開始・終了はどちらのオフィスであっても良いものとします。

制約

  • 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 は整数である

入力

入力は以下の形式で標準入力から与えられる。

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

3 2 1 1
1 10
10 1
1 10
1 2
2 3

出力例 1

6

入力例 2

3 0 1 1
1 10
10 1
1 10

出力例 2

4

入力例 3

3 2 100 100
1 10
10 1
1 10
3 2
2 1

出力例 3

12

入力例 4

4 4 3 8
100 1
1 100
1 100
100 1
1 2
1 3
2 4
3 4

出力例 4

23