TopCoder

Caido
Waimai

User's AC Ratio

25.0% (4/16)

Submission's AC Ratio

4.1% (11/268)

Tags

Description

**測資有誤QQ (應該修正好了 2019/11/18)

某天眼皮醬跟起司豬在討論某種邪教咒語的規律
「聽起來好洗腦喔~」
「怎麼都在那幾個音跳來跳去~」
「你不要再放了,你每天放我都快要可以背起來了!」
「亞八里~亞八里~向姊轉轉~」
「這段咒語的結尾可以直接接到另外那段咒語的開頭耶!」
「不要跟著節奏轉肚皮啦!」
「轉~轉~轉~」
「是說既然可以咒語之間有連結關係,那我們可以把咒語接起來咯~」
「那我們可以把咒語接成多長啊?」

這時候問題就來了
給你一堆邪教咒語,還有之間的連接關係,問你可以把咒語接的多長(咒語可以重複使用)?
為了方便計算,我們把咒語切成許多等長的音

Input Format

每個檔案開頭有一個整數T,代表這個檔案接下來有幾筆測資
每筆測資開頭有兩個整數N,M,代表有N條咒語,咒語之間的關係有M
接下來的一行有N個數字a1,a2,a3...ai...aN,代表咒語i的長度
接下來M行,每行四個數字s1,t1,s2,t2,代表咒語s1t1個音結束的瞬間可以直接接到s2t2個音的前面

1 ≦ T ≦ 10
1 ≦ N ≦ 105
0 ≦ M ≦ 5*105
1 ≦ ai ≦ 108
1 ≦ s1,s2N
1 ≦ t1as1
1 ≦ t2as2

有30%的測資1 ≦ N,M ≦ 103 且 1 ≦ ai ≦ 103
有60%的測資1 ≦ N,M ≦ 104 且 1 ≦ ai ≦ 108

Output Format

對每筆測資請輸出重新組合後的咒語最多會有多少個音
如果長度是無限長的話,請輸出"LoveLive!"(不含引號)
每筆測資之間要換行

Sample Input 1

2
3 3
10 10 10
1 5 2 3
2 7 1 6
2 3 3 5
1 1
10
1 6 1 3

Sample Output 1

15
LoveLive!

Hints

Problem Source

2015建中校隊入隊考試-複試

Subtasks

No. Testdata Range Score
1 0 30
2 0~1 30
3 0~4 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 262144 1 2 3
1 2000 262144 262144 2 3
2 5000 262144 262144 3
3 3000 262144 262144 3
4 2000 262144 262144 3