Cups and Beans

Time limit1sMemory limit256 MB

Summary

Beans sit in cups 1 through N-1, each with a move limit C_i; players alternate sliding one bean to a lower cup and whoever cannot move loses. Decide the winner.

Level: Hard8 of 10
Topics: Game theory, Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

There are $N$ cups numbered 0 through $N-1$ . For each $i$ ( $1 \leq i \leq N-1$ ), cup $i$ contains $A_i$ beans, and this cup is labeled with an integer $C_i$ .

Two people play the following game:

In each turn, the player chooses a bean from one of the cups except cup $0$ .
If he chooses a bean from cup $i$ , he must move it to one of the cups $i-C_i, \ldots, i-1$ .
The players take turns alternately. If a player can't choose a bean, he loses.

Who wins if both players play optimally?

Input

$N$
$C_1$ $A_1$
$C_2$ $A_2$
$\vdots$
$C_{N-1}$ $A_{N-1}$

Output

Print the name of the winner: "First" or "Second".

Constraints

$2 \leq N \leq 10^5$
$1 \leq C_i \leq i$
$0 \leq A_i \leq 10^9$
At least one of $A_i$ is nonzero.
All values in the input are integers.

Hint

Notes on Sample 1:

In the first turn, the first player must move a bean from $2$ to $1$ .
In the second turn, the second player must move a bean from $1$ to $0$ .
In the third turn, the first player can't choose a bean and loses.

Examples3

Example 1
Input
```
3
1 0
1 1
```
Expected output
```
Second
```
Example 2
Input
```
7
1 1
2 0
1 0
2 0
4 1
3 0
```
Expected output
```
First
```
Example 3
Input
```
7
1 1
2 0
1 9
2 10
4 3
3 5
```
Expected output
```
Second
```