F - カード集め

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

机の上に N 枚のカードがあり、それぞれ 1 から N まで番号付けられています。

これらのカードを用いて 2 人で以下のゲームを行います。

  • 先手から交互にカードを 1 枚ずつ机の上から取ります。
  • 机の上のカードが全て取られたらゲームは終了します。

その後、以下のルールに従ってスコア計算を行い、勝者を決定します。

  • i (1 \leq i \leq N) 番目のカードを取ったプレイヤーがスコア s_i を得る。
  • i = 1, 2, ..., M について、a_i 番目のカードと b_i 番目のカードをどちらも取ったプレイヤーがスコア c_i を得る。

その結果、合計スコアが大きいプレイヤーが勝者となり、合計スコアが同じ場合は後手が勝者となります。

勝者となるためにお互いが最適に行動したとき、どちらが勝者となるでしょうか。

制約

  • 入力は全て整数である。
  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq a_i < b_i \leq N
  • 1 \leq s_i, c_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N M
s_1 s_2 ... s_N
a_1 b_1 c_1
a_2 b_2 c_2
:
a_M b_M c_M

出力

先手が勝者となる場合 First を、後手が勝者となる場合 Second を出力せよ。


入力例 1

4 4
1 20 30 10
1 2 40
1 3 30
1 4 50
2 3 100

出力例 1

First
  • 先手は初めに 1 番目のカードを取ります。
  • 次に、後手が 2 番目のカードを取った場合を考えます。
  • このとき、先手は 3 番目のカードを取ります。
  • すると、後手は 4 番目のカードを取るしかありません。

そのときの合計スコアは次のようになり、先手が勝者となります。

  • 先手は 1 番目と 3 番目のカードを取ったので、先手の合計スコアは 1 + 30 + 30 = 61 です。
  • 後手は 2 番目と 4 番目のカードを取ったので、後手の合計スコアは 20 + 10 = 30 です。

他の場合も先手が上手く取ることで、先手が勝者となります。


入力例 2

6 10
16 14 5 2 6 11
1 2 17
1 3 8
1 6 7
2 3 2
2 4 1
2 6 9
3 4 3
3 5 2
4 5 17
5 6 26

出力例 2

Second

入力例 3

10 9
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000

出力例 3

Second