問題文

ハシモトくんは、 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 は整数である

入力例 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