AT_tenka1_2016_final_d 右往左往

# 右往左往 桥本君被分配了 $N$ 个任务，每一个任务 $i$ 总共需要 $A_{i}$ 的时间在第一个办公室内完成， $B_{i}$ 的时间在第二个办公室内完成。在两个办公室间的第$n$次转换需要消耗 $C*(n-1)+D$ 的时间。 此外，各个任务间存在 $M$ 个相互关系：任务 $Y_{i}$ 必须在任务 $X_{i}$ 完成后才可以进行。 桥本君想要在最短的时间内完成所有任务，总共需要多长的时间？ 注：任务处理可以在任意一个办公室开始和结束。

第一行：$N$,$M$,$C$,$D$，以空格隔开。 下面$N$行：每行两个整数 $A_{i}$,$B_{i}$，以空格隔开。 接下来$M$行：每行两个整数 $X_{i}$,$Y_{i}$，以空格隔开。

输出一行，一个整数，表示桥本君所需要的最短时间。 ## 输入输出样例 ## 样例 #1 ### 样例输入 #1 ``` 3 2 1 1 1 10 10 1 1 10 1 2 2 3 ``` ### 样例输出 #1 ``` 6 ``` ## 样例 #2 ### 样例输入 #2 ``` 3 0 1 1 1 10 10 1 1 10 ``` ### 样例输出 #2 ``` 4 ``` ## 样例 #3 ### 样例输入 #3 ``` 3 2 100 100 1 10 10 1 1 10 3 2 2 1 ``` ### 样例输出 #3 ``` 12 ``` ## 样例 #4 ### 样例输入 #4 ``` 4 4 3 8 100 1 1 100 1 100 100 1 1 2 1 3 2 4 3 4 ``` ### 样例输出 #4 ``` 23 ```

- $ 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 $ - $M$ 个关系间不会存在循环 - $ N $, $ M $, $ C $, $ D $, $ A_i $, $ B_i $, $ X_i $, $ Y_i $ 均为正整数