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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n, f;
int field[10][10];
int memo[3][2][1 << 16][8];
int win;

int GetP(int fs, int turn, int prev, int next) {
  int ret = 0;
  if (turn != 0) {
    if (fs == 0) {
      ret = field[next][prev];
    } else {
      ret = field[prev][next];
    }
  }
  return ret;
}

int calc(int yowai, int fs, int use, int prev) {
  int turn = __builtin_popcount(use);
  if (turn == 2 * n) { return f; }
  if (memo[yowai][fs][use][prev] != -1) { return memo[yowai][fs][use][prev]; }
  int used = 0;
  if (fs == 0) {
    used = use & ((1 << n) - 1);
  } else {
    used = (use >> n) & ((1 << n) - 1);
  }
  int ret = -10000000;
  if (yowai == fs) { ret = 10000000; }
  REP(i, n) {
    int nused = used | (1 << i);
    if (used == nused) { continue; }
    int nret = GetP(fs, turn, prev, i);
    int nuse = use | (nused << (fs * n));
    nret -= calc(yowai, fs ^ 1, nuse, i);
    if (yowai == fs) {
      ret = min(ret, nret);
    } else {
      ret = max(ret, nret);
    }
  }
  return memo[yowai][fs][use][prev] = ret;
}

int Search(int fs, int use, int prev, int p, int beta, int alpha) {
  int turn = __builtin_popcount(use);
  if (turn == 2 * n) { return 2 * n; }
  if (p + calc(fs ^ 1, fs, use, prev) < 0) { return turn + 1; }
  int used = 0;
  if (fs == 0) {
    used = use & ((1 << n) - 1);
  } else {
    used = (use >> n) & ((1 << n) - 1);
  }
  int ret = turn + 1;
  if (win == fs) { ret = 100; }
  REP(i, n) {
    if (beta <= alpha) { break; }
    int nused = used | (1 << i);
    if (used == nused) { continue; }
    int np = p + GetP(fs, turn, prev, i);
    int nuse = use | (nused << (fs * n));
    if (win == fs && np - calc(2, fs ^ 1, nuse, i) < 0) { continue; }
    int nret = Search(fs ^ 1, nuse, i, -np, beta, alpha);
    if (win == fs) {
      ret = min(ret, nret);
      beta = min(beta, ret);
    } else {
      ret = max(ret, nret);
      alpha = max(alpha, ret);
    }
  }
  return ret;
}

int main() {
  while (scanf("%d %d", &n, &f) > 0) {
    MEMSET(memo, -1);
    REP(y, n) {
      REP(x, n) {
        scanf("%d", &field[y][x]);
      }
    }
    int ans = calc(2, 0, 0, 0);
    if (ans > 0) {
      win = 0;
      puts("First");
      printf("%d\n", Search(0, 0, 0, 0, 100, -100));
    } else if (ans == 0) {
      puts("Draw");
      printf("%d\n", 2 * n);
    } else {
      win = 1;
      puts("Second");
      printf("%d\n", Search(0, 0, 0, 0, 100, -100));
    }
  }
}