April, the reigning monarch of Mayland, is planning this years March March. March March is an annual tradition for the monarchy travel between the various cities of Mayland, following the same track as this year's Iditarod.
Mayland consists of $$$n$$$ cities, labelled $$$1 \ldots n$$$. Historically, these labels represented a ranking of the cities. To show off the kingdom in its best light, the March March starts off by visiting cities in order: starting at city $$$1$$$, then city $$$2$$$, then eventually ending at city $$$n$$$, in the hopes that by then, most people have already lost interest and gone home.
However, times are changing. As the March March gets more and more extravagant, only $$$m$$$ one-way roads between the cities are suitable for use in the March March. Moreover, some of these labels haven't been changed in centuries, and may no longer be accurate for today's cities! April is concerned: it might not even be possible to hold a proper March March this year, which would also ruin the sled race!
Thankfully, April has an idea. She can use some of the Mayland's treasury to construct a new one way road from any city to any other, for a price of $$$c$$$. However, she may be able to spare some money by changing the labels of cities! Of course, a city $$$i$$$ will happily take a new label $$$j$$$ if $$$j \lt i$$$. But to appease the citizens, April will need to pay $$$d$$$ to convince a city to take on a worse label. April wonders: what is the cheapest way she can make this years March March a success?
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 20, 1 \leq m \leq \frac{n(n-1)}{2}$$$), representing the number of cities and one-way roads, respectively.
The second line contains two integers, $$$c$$$ and $$$d$$$ ($$$1 \leq c,d \leq 10^6$$$), representing the cost to build a one-way road and the cost to convince a city to assume a worse ranking, respectively. All roads will be distinct.
Finally, the last $$$m$$$ lines contain two integers $$$a$$$ and $$$b$$$ each ($$$1 \leq a,b \leq n, a \not= b$$$), representing a one-way road that already exists from city $$$a$$$ to city $$$b$$$.
Output a single integer, the minimum cost needed to make a suitable March March.
6 5 3 5 1 2 2 3 3 5 5 4 4 6
5
6 5 3 10 1 2 2 3 3 5 5 4 4 6
9
In the first case, it is optimal for April to relabel city $$$4$$$ to city $$$5$$$, and city $$$5$$$ to city $$$4$$$. She does not need to build any roads, so she only pays $$$5$$$ total to convince city $$$4$$$ to take a worse label.
In the second case, the cost of relabelling cities has gone up. It is now optimal for April to just build roads from $$$3$$$ to $$$4$$$, $$$4$$$ to $$$5$$$, and $$$5$$$ to $$$6$$$.
