Problem7283--AtCoder Educational DP Contest —— K - Stones

7283: AtCoder Educational DP Contest —— K - Stones

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 1Submit Num: 1StatisticsShowOff!

Description

There is a set $A = \{ a_1, a_2, \ldots, a_N \}$ consisting of $N$ positive integers. Taro and Jiro will play the following game against each other.
Initially, we have a pile consisting of $K$ stones. The two players perform the following operation alternately, starting from Taro:
  • Choose an element $x$ in $A$, and remove exactly $x$ stones from the pile.
A player loses when he becomes unable to play. Assuming that both players play optimally, determine the winner.

Input

Input is given from Standard Input in the following format:
$N\ K$
$a_1\ a_2\ \ldots\ a_N$

Output

If Taro will win, print First; if Jiro will win, print Second.

Constraints

All values in input are integers.
$1 \leq N \leq 100$
$1 \leq K \leq 10^5$
$1 \leq a_1 < a_2 < \cdots < a_N \leq K$

Sample 1 Input 

2 4
2 3

Sample 1 Output 

First
If Taro removes three stones, Jiro cannot make a move. Thus, Taro wins.

Sample 2 Input 

2 5
2 3

Sample 2 Output 

Second
Whatever Taro does in his operation, Jiro wins, as follows:
  • If Taro removes two stones, Jiro can remove three stones to make Taro unable to make a move.
  • If Taro removes three stones, Jiro can remove two stones to make Taro unable to make a move.

Sample 3 Input 

2 7
2 3

Sample 3 Output 

First
Taro should remove two stones. Then, whatever Jiro does in his operation, Taro wins, as follows:
  • If Jiro removes two stones, Taro can remove three stones to make Jiro unable to make a move.
  • If Jiro removes three stones, Taro can remove two stones to make Jiro unable to make a move. 

3 20
1 2 3


Second

Sample 4 Input 

3 21
1 2 3

Sample 4 Output 

First

Source/Category

博弈论 
Submit