2151 . 大富翁
TopCoder
Description
小凱最喜歡玩大富翁了！
大富翁的盤面是由$N$個編號$1$到$N$城市和$M$條單向的飛機航線組成，其中搭乘飛機航線是唯一可以由一個城市到達另外一個城市的交通方式。注意不會有航線的起點和終點是同一個城市。也沒有兩條航線，他們的起點相同、終點也相同。而且因為是大富翁，所以每個城市都至少可以透過一條航線離開該城市(有終點的遊戲就不是大富翁了)。此外，小凱對每個城市都有著各自的喜好度，其中他對編號為$i$的城市之喜好度為$c_i$(如果是正的就代表他喜歡，負的就代表他討厭)。
小凱今天跟往常一樣，獨自一人孤單地玩著大富翁。他首先決定了兩個正整數$s$、$t$，代表他今天的起點是編號為$s$的城市，而他總共要玩$t$回合。此外，他一開始的開心程度為$0$。在每一回合，他會從他原本在的城市透過一條航線到達另一個城市(注意他每一回合都必須移動)，而他的開心程度就會加上他對那個新抵達的城市的喜好度。
你是小凱的好朋友，但你覺得這個大富翁無聊到根本不能被稱為一個遊戲，你唯一關注的就是在玩完$t$回合之後，小凱的開心程度最大能有多大。
Input Format
第一行有四個正整數$N$、$M$、$s$、$t$意義如題序所述。
第二行有$N$個以空白隔開的整數$c_1,c_2,\cdots,c_N$。
接下來有$M$行，其中第$i$行有兩個以空白隔開之正整數$u_i$、$v_i$，代表存在一條起點為$u_i$，終點為$v_i$之航線。
對於所有測資，$2 \leq N \leq 200,M \leq N \times(N-1),1\leq s \leq N,t \leq 10^ {14}, $
$-1000 \leq c_i \leq 1000,1 \leq u_i,v_i \leq N$。
Output Format
請輸出一個整數於一行，代表在經過$t$回合之後，小凱的開心程度最大能有多大。
Sample Input 1
3 4 1 1 10 1 2 1 2 1 3 2 3 3 2
Sample Output 1
2
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~8 | 每個城市都只有一條航線可以離開，而且每個城市都可以透過搭乘數次飛機航線到達其他所有城市 | 9 |
| 2 | 9~19 | $N \leq 10,M \leq 20,t \leq 5$ | 14 |
| 3 | 9~30 | $t \leq 1000$ | 32 |
| 4 | 0~43 | 無額外限制 | 45 |