← 返回题目列表

AtCoder · tenka1_2016_final_d

D. 左右

中文机器翻译题面 查看原题

配点 : 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