Problem Description

Hashimoto is assigned \( N \) tasks.

Task \( i \) takes \( A_i \) time if worked on in the first office, and \( B_i \) time if worked on in the second office.

The \( n \)-th trip between offices takes \( C \times (n - 1) + D \) time.

There are also \( M \) dependencies between tasks, where task \( X_i \) must be completed before task \( Y_i \) can be started.

What is the minimum time required for Hashimoto to complete all tasks if he acts optimally?

Note that starting and ending tasks can be done in either office.

Input Format

The input is given from the standard input in the following format:

\( 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 \)

Output Format

Output the minimum time required for Hashimoto to complete all tasks in one line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

6

Sample Input #2

3 0 1 1
1 10
10 1
1 10

Sample Output #2

4

Sample Input #3

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

Sample Output #3

12

Sample Input #4

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

Sample Output #4

23

Notes/Hints

Constraints

• \( 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 \)
• If \( i \neq j \), then \( X_i \neq X_j \) or \( Y_i \neq Y_j \)
• There are no cycles in the task dependencies
• \( N \), \( M \), \( C \), \( D \), \( A_i \), \( B_i \), \( X_i \), \( Y_i \) are integers

见题面 Input 部分

见题面 Output 部分