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