Problem: Problem statement

Two players are playing the game. The rules of the game will be described below.

There is a board of $ N × N $ squares, and each square has the number $ X_ {i, j} $ ($ 1 \ leq i, j \ leq N $) written on it. The first move and the second move alternately select hands and accumulate points. The first move has $ F $ points and the second move has $ 0 $ points.

$ t $ Shows the player's actions on the turn ($ 1 \ leq t \ leq 2N $).

1. If you lose, no matter what move you and your opponent choose, immediately declare the loss and end the game.
2. Choose a number from $ 1,2, ..., N $ that you have never chosen and use it as $ Y_t $.
1. When the first move (that is, $ t $ is odd) and $ t> 1 $, the first move gets $ X_ {Y_ {t}, Y_ {t-1}} $ points. When $ t = 1 $, there is no change in the score of the first move.
2. When it is the second move (that is, $ t $ is an even number), the second player gets $ X_ {Y_ {t-1}, Y_ {t}} $ points.
3. When $ t = 2N $, win / loss judgment is made and the game ends. If the player who has the most points wins and the points are the same, it is a draw.
4. End the turn and give your opponent a turn.



The first move and the second move are selected based on the following criteria.

1. If there is a move that you can win, choose that move. If there are multiple moves that you can win, choose the move that will end the game in the shortest time.
2. If you don't have a winning move, choose a draw if you have one.
3. Choose a move that will end the game at the longest when you have only a losing move.



Find out the outcome of the game and how many turns the game will end when the first move and the second move choose their moves based on these criteria.

Constraint

* $ 1 \ leq N \ leq 8 $
* $ -10 ^ 5 \ leq F \ leq 10 ^ 5 $
* $ -10 ^ 5 \ leq X_ {i, j} \ leq 10 ^ 5 $



input

Input follows the following format. All given numbers are integers.


$ N $ $ F $
$ X_ {1,1} $ $ X_ {1,2} $ $ ... $ $ X_ {1, N} $
$ X_ {2,1} $ $ X_ {2,2} $ $ ... $ $ X_ {2, N} $
$ ... $
$ X_ {N, 1} $ $ X_ {N, 2} $ $ ... $ $ X_ {N, N} $

output

Output "First" if the first move wins, "Second" if the second move wins, and "Draw" if it is a draw. Print on the second line how many turns the game will end.

Examples

Input

2 0
1 3
1 1


Output

Second
3


Input

2 100
0 0
0 0


Output

First
2


Input

2 5
3 4
7 6


Output

Draw
4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int UKU=LLONG_MAX/2;
const int INF=1001001001001001001ll;

int N,F;
int X[10][10];

int M[1<<8][1<<8][8];
int m[1<<8][1<<8][8];
int dp[1<<8][1<<8][8];
int calcM(int b,int bb,int pr,int t){
    int &ret=M[b][bb][pr];
    if(ret!=UKU)return ret;
    ret=-INF;
    if(t==2*N+1){
        ret=0;
    }
    else if(t&1){
        rep(i,N){
            if(b>>i&1)continue;
            int tmp=calcM(b|(1<<i),bb,i,t+1);
            if(t!=1)tmp+=X[i][pr];
            chmax(ret,tmp);
        }
    }
    else{
        rep(i,N){
            if(bb>>i&1)continue;
            int tmp=calcM(b,bb|(1<<i),i,t+1);
            tmp-=X[pr][i];
            chmax(ret,tmp);
        }
    }
    return ret;
}

int calcm(int b,int bb,int pr,int t){
    int &ret=m[b][bb][pr];
    if(ret!=UKU)return ret;
    ret=INF;
    if(t==2*N+1){
        ret=0;
    }
    else if(t&1){
        rep(i,N){
            if(b>>i&1)continue;
            int tmp=calcm(b|(1<<i),bb,i,t+1);
            if(t!=1)tmp+=X[i][pr];
            chmin(ret,tmp);
        }
    }
    else{
        rep(i,N){
            if(bb>>i&1)continue;
            int tmp=calcm(b,bb|(1<<i),i,t+1);
            tmp-=X[pr][i];
            chmin(ret,tmp);
        }
    }
    return ret;
}


int calcdp(int b,int bb,int pr,int t){
    int &ret=dp[b][bb][pr];
    if(ret!=UKU)return ret;
    if(t==2*N+1){
        ret=0;
    }
    else if(t&1){
        ret=-INF;
        rep(i,N){
            if(b>>i&1)continue;
            int tmp=calcdp(b|(1<<i),bb,i,t+1);
            if(t!=1)tmp+=X[i][pr];
            chmax(ret,tmp);
        }
    }
    else{
        ret=INF;
        rep(i,N){
            if(bb>>i&1)continue;
            int tmp=calcdp(b,bb|(1<<i),i,t+1);
            tmp-=X[pr][i];
            chmin(ret,tmp);
        }
    }
    return ret;
}

int ei[1<<8][1<<8][8];

int latte(int b,int bb,int pr,int t,int tx){
    if(t==tx){
        if(tx&1)return -M[b][bb][pr];
        return -m[b][bb][pr];
    }
    int &ret=ei[b][bb][pr];
    if(ret!=UKU)return ret;

    if(t&1){
        ret=INF;
        rep(i,N){
            if(b>>i&1)continue;
            int tmp=latte(b|(1<<i),bb,i,t+1,tx);
            if(t!=1)tmp-=X[i][pr];
            chmin(ret,tmp);
        }
    }
    else{
        ret=-INF;
        rep(i,N){
            if(bb>>i&1)continue;
            int tmp=latte(b,bb|(1<<i),i,t+1,tx);
            tmp+=X[pr][i];
            chmax(ret,tmp);
        }
    }
    return ret;
}


signed main(){
    N=8;F=0;
    cin>>N>>F;
    rep(i,N)rep(j,N)cin>>X[i][j];

    fill_n(**M,(1<<8)*(1<<8)*8,UKU);
    fill_n(**m,(1<<8)*(1<<8)*8,UKU);
    fill_n(**dp,(1<<8)*(1<<8)*8,UKU);

    calcM(0,0,0,1);
    calcm(0,0,0,1);
    calcdp(0,0,0,1);

    if(dp[0][0][0]+F==0){
        cout<<"Draw"<<endl;
        cout<<2*N<<endl;
        return 0;
    }

    if(dp[0][0][0]+F>0){
        cout<<"First"<<endl;
        for(int i=2;i<=2*N;i+=2){
            fill_n(**ei,(1<<8)*(1<<8)*8,UKU);
            if(latte(0,0,0,1,i)<F){
                cout<<i<<endl;
                return 0;
            }
        }
    }
    else{
        cout<<"Second"<<endl;
        for(int i=1;i<=2*N;i+=2){
            fill_n(**ei,(1<<8)*(1<<8)*8,UKU);
            if(latte(0,0,0,1,i)>F){
                cout<<i<<endl;
                return 0;
            }
        }
    }

    return 0;
}