B - 宝石の分配 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 266 点

問題文

高橋君と青木君は、ベルトコンベアで流れてくる宝石を分配するゲームをしています。

ゲームのはじめに、正の整数 K が決められています。これは、高橋君が取る宝石の価値の合計の上限です。

N 個の宝石が 1 番目から N 番目まで順番にベルトコンベアで流れてきます。i 番目に流れてくる宝石の価値は A_i（正の整数）です。

高橋君は、宝石が流れてくるたびに、以下のルールに従ってその宝石を取るかどうかが決まります：

  • その宝石を取ったとしても、これまでに取った宝石の価値の合計（その宝石を含む）が K 以下であるならば、その宝石を取る。
  • そうでない場合（その宝石を取ると合計が K を超えてしまう場合）は、その宝石を取らない。

すなわち、高橋君は先頭から順に、合計が K を超えない限り貪欲に宝石を取り続けます。

青木君は、高橋君が取らなかった宝石をすべて受け取ります。青木君に選択権はありません。

N 個の宝石がすべて流れ終わった後、高橋君が取った宝石の価値の合計と、青木君が受け取った宝石の価値の合計を比較します。合計が大きい方が勝ちで、合計が同じ場合は引き分けとなります。

宝石の個数 N、上限値 K、および N 個の宝石の価値の列 A_1, A_2, \ldots, A_N が与えられたとき、ゲームの結果を判定してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{15}
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N K
A_1 A_2 \ldots A_N
  • 1 行目には、宝石の個数を表す整数 N と、高橋君が取る宝石の価値の合計の上限を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、流れてくる順番に並んだ N 個の宝石の価値 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

高橋君が勝つ場合は Takahashi 、青木君が勝つ場合は Aoki 、引き分けの場合は Draw を 1 行で出力してください。

入力例 1

5 10
3 4 2 8 1

出力例 1

Takahashi

入力例 2

6 5
2 4 3 1 5 3

出力例 2

Aoki

入力例 3

8 15
5 3 4 6 2 7 1 2

出力例 3

Draw

Score : 266 pts

Problem Statement

Takahashi and Aoki are playing a game where they distribute gems flowing on a conveyor belt.

At the beginning of the game, a positive integer K is determined. This is the upper limit on the total value of gems that Takahashi can take.

N gems flow on the conveyor belt in order, from the 1-st to the N-th. The value of the i-th gem is A_i (a positive integer).

Each time a gem flows by, whether Takahashi takes it is determined according to the following rules:

  • If taking the gem would keep the total value of gems he has taken so far (including this gem) at most K, he takes the gem.
  • Otherwise (if taking the gem would cause the total to exceed K), he does not take the gem.

In other words, Takahashi greedily takes gems in order from the first, as long as the total does not exceed K.

Aoki receives all the gems that Takahashi did not take. Aoki has no choice in the matter.

After all N gems have flowed by, the total value of gems Takahashi took and the total value of gems Aoki received are compared. The one with the greater total wins, and if the totals are equal, it is a draw.

Given the number of gems N, the upper limit K, and the sequence of values of the N gems A_1, A_2, \ldots, A_N, determine the result of the game.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{15}
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N K
A_1 A_2 \ldots A_N
  • The first line contains the integer N representing the number of gems and the integer K representing the upper limit on the total value of gems Takahashi can take, separated by a space.
  • The second line contains the values of the N gems A_1, A_2, \ldots, A_N in the order they flow by, separated by spaces.

Output

If Takahashi wins, print Takahashi; if Aoki wins, print Aoki; if it is a draw, print Draw, on a single line.

Sample Input 1

5 10
3 4 2 8 1

Sample Output 1

Takahashi

Sample Input 2

6 5
2 4 3 1 5 3

Sample Output 2

Aoki

Sample Input 3

8 15
5 3 4 6 2 7 1 2

Sample Output 3

Draw