你是一位列車長，正在駕駛著一台火車開往左營。但是，不知名的魔法師施法讓鐵道上充滿了紓壓好玩的泡泡紙。
火車路網圖可以由一張有 $N$ 個節點的有向圖表示，其中，左營的編號為 $N$ 。對於第 $i$ 個節點的第 $j$ 條邊，它會有兩個參數 $t_{i,j},w_{i,j}$ ，分別表示那一條鐵道指向的節點以及這條鐵道的泡泡紙數量。
此外，對於每一個節點，剛開始時會由一個指針指著自己的第 $1$ 條鐵道。當火車抵達這個節點的時候，如果該節點不是 $N$ 號點，則火車會走向指針所指的鐵道。
但是，更換指針並不是不可能的。對於第 $i$ 個節點，如果付 $a_i$ 元給管理員，則它會將指針往右搬動 $x_i$ 格，而如果付 $b_i$ 元給管理員，則他會將指針往右搬動 $y_i$ 格，對於第 $i$ 個節點，移動指針的花費不能超過 $c_i$ 元。注意到，如果向右搬動之後超出該點的鐵道數量的話，會繞回第一條鐵道繼續搬動（也就是說，假設指針目前在 $p$ ，第 $i$ 個點出度為 $d_i$，那付一次 $a_i$ 元可以把 $p$ 變為 $(p+x_i-1)\text{ mod }d_i+1$，付一次 $b_i$ 元可以把 $p$ 變為 $(p+y_i-1)\text{ mod }d_i+1$）。可以付多次 $a_i$ 與 $b_i$ 來搬動指針
身為一位盡責的列車長，當你從出發站前往左營時，你抵達左營所經過的距離必須是在所有合法移動指針的方法中，該點至左營的最短距離，也就是說，不能存在一條路徑長度比你所走的路徑還要短。
你最喜歡泡泡紙被火車那強壯有力的輪子輾過所發出的哀嚎了，因此，你想要知道，對於所有車站，如果你都沿著最短路徑走，並且在第 $i$ 個車站花費不超過 $c_i$ 元，則你最多可以壓過多少張泡泡紙？
但是，鐵路會有無法抵達左營的情況，或者是無法在各節點花費分別不超過 $c_i$ 的情況抵達的狀況，此時，請輸出 -1。
第一行輸入一個整數 $N$ ，表示車站數量。
接下來輸入 $N$ 行，每行分別代表一個車站的鐵道。
第 $i+1$ 行首先輸入一個整數 $d_i$，表示第 $i$ 個車站的鐵道數量。接下來輸入 $2 \times d_i$ 個整數，第 $2j,2j+1$ 個整數分別代表該鐵道指向的車站以及泡泡紙數量 $t_{i,j},w_{i,j}$。
接下來輸入一行 $N$ 個整數，分別代表 $a_i$。
接下來輸入一行 $N$ 個整數，分別代表 $x_i$。
接下來輸入一行 $N$ 個整數，分別代表 $b_i$。
接下來輸入一行 $N$ 個整數，分別代表 $y_i$。
接下來輸入一行 $N$ 個整數，分別代表 $c_i$。
對於所有測試資料：
輸出 $N$ 行，第 $i$ 行代表在所有合法移動指針的方法中，由第 $i$ 個節點沿著最短路徑到左營，可以壓過的最大泡泡紙數量。
如果無解請輸出 -1。
對於第一筆範例的第一個點，最佳解為先花費 $1$ 元把指針由第一條鐵道改到第 $(1+3-1)\text{ mod }4 +1 = 4$ 條邊，再花 $1$ 元把指針移動到第 $(4+3-1)\text{ mod }4+1 = 3$ 條邊。之後移動到 $4$ 號點。在 $4$ 號點不花錢，直接移動到 $6$ 號點。路上輾過 $8$ 張泡泡紙。
對於 $6$ 號點，由於本身就是左營故最短路徑為 $0$，因此不能移動。
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 2~11 | $a_i = b_i > c_i$ | 11 |
| 3 | 1, 12~21 | $x_i = y_i= 1,b_i = a_i,N \le 500$ | 13 |
| 4 | 1, 12~31 | $x_i = y_i = 1,b_i = a_i$ | 15 |
| 5 | 0~1, 12~41 | $a_i = b_i,x_i = y_i$ | 17 |
| 6 | 0~1, 12~21, 42~51 | $N \le 500$ | 19 |
| 7 | 0~61 | 無其他限制 | 25 |