- 21.84%
- 2000ms
- 262144K

Morgana is playing a game called End Fantasy VIX. In this game, characters have $n$ skills, every skill has its damage. And using skill has special condition. Briefly speaking, if this time you use skill `"x"`

, then next time you can use skill `"y"`

(just like combo). There are $m$ conditions ($x_i$, $y_i$), and you can't break the rules. (that means, if you don't have any condition that equals to ($x$, $y$), then you can't use `"y"`

after use `"x"`

).

Now, Morgana wants to defeat the boss, he can use skills t times. In the first time he can use any skill, then he should obey the rules. Besides, he has a special armor called "Xue La", he can use this armor and add a debuff to the boss. The debuff will record damage and when it is over, the record damage will be caused again. (that means double damage) The debuff will continue $T$ times, and he can use this armor in any time, it won't be in conflict with skills.

Finally, Morgana wants to maximize the damage, but it is too difficult. So please help him deal with this problem.

(If Morgana can not use any skill at a time, he will finish the game and the final damage is his total damage at this time.)

First line contains $4$ integers $n,m,t,T$ ($2 \le n \le 64$, $1 \le m \le n \times (n-1)$ , $1 \le t \le 1e9$, $1 \le T \le t$).

In the next $m$ lines each line contains two integers represent condition ($x_i, y_i$) ($x_i, y_i \le n$) .

Then the next line contains $n$ integers represent the damage of the skills (every skill's damage is smaller than $1e8$).

One line with one integer.

2 2 3 3 1 2 2 1 1 2

10