小凱最喜歡玩大富翁了！

大富翁的盤面是由$N$個編號$1$到$N$城市和$M$條單向的飛機航線組成，其中搭乘飛機航線是唯一可以由一個城市到達另外一個城市的交通方式。注意不會有航線的起點和終點是同一個城市。也沒有兩條航線，他們的起點相同、終點也相同。而且因為是大富翁，所以每個城市都至少可以透過一條航線離開該城市(有終點的遊戲就不是大富翁了)。此外，小凱對每個城市都有著各自的喜好度，其中他對編號為$i$的城市之喜好度為$c_i$(如果是正的就代表他喜歡，負的就代表他討厭)。

小凱今天跟往常一樣，獨自一人孤單地玩著大富翁。他首先決定了兩個正整數$s$、$t$，代表他今天的起點是編號為$s$的城市，而他總共要玩$t$回合。此外，他一開始的開心程度為$0$。在每一回合，他會從他原本在的城市透過一條航線到達另一個城市(注意他每一回合都必須移動)，而他的開心程度就會加上他對那個新抵達的城市的喜好度。

你是小凱的好朋友，但你覺得這個大富翁無聊到根本不能被稱為一個遊戲，你唯一關注的就是在玩完$t$回合之後，小凱的開心程度最大能有多大。