文理学院程序设计在线练习


新游戏

Time Limit: 2 Second(s)    Memory Limit: 32 MB

Total Submission(s): 204   Accepted Submission(s): 64
Problem Description

小希在和小朵玩一个简单的新游戏:
有n个物品放在她们面前,每个人轮流,每轮选择一个归为己有(显然,选择的是最有利于自己的),第i件物品对于小希来说价值ai,对于小朵来说价值bi
小希先拿,如果最终小希得到的总价值减去小朵得到的总价值小于w,那么小朵获胜,否则小希获胜。

Input

第一行输入一个整数T,表示数据组数(T<=1200)。
每组数据第一行输入两个整数n,w,分别代表物品的数量和价值差。
随后n行,每行两个整数,分别代表第i件物品对于小希的价值ai和对于小朵的价值bi。其中,
1 <= n <= 1000,
-1000000000 <= ai,bi,w <= 1000000000。

Output

对于每组数据输出一行,如果小希会胜利,则输出”xi”,否则,则输出”duo”。注意:引号不必输出。

Sample Input
2
2 1000
5000 0
0 500
2 1
1 5
2 4
Sample Output
xi
duo
Hint

样例1中,小希选择第一件物品,得到5000,小朵选择第二件物品,得到500,小希得到的价值-小朵得到的价值=5000-500=4500>=1000。
样例2中,显然小希无论如何都会惨败。

Source

2019校赛