Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Cheat in the Game
Time Limit: 6000MSMemory Limit: 65536K
Total Submissions: 1149Accepted: 380

Description

Alice and Bob are playing a game. At the beginning, the judge takes out a stone pile of W stones and a black box containing N cards. Every card has a number Ai on it. Alice and Bob takes turns to draw a card from the box. Of course, they will not know the number until they draw the card out of the box. The player then takes away Ai stones from the pile if it is possible. If there are not enough stones, the player draws a card again. The winner is the player who takes away the last stone. Once the box gets empty, they brings back all cards and stones and play the game again until there is a winner.

Now your best friend Alice begs you, the judge, to help her cheat in the game. You have already known the number of cards in the box and their numbers. Given a integer M, You want to know how many values, less or equal to M, W can take so that you can make sure Alice will be the winner of the game.

Input

There are several test cases.
The first line of each test case contains two integers N (1 ≤ N ≤ 10000) and M (1 ≤ M ≤ 100000).
The second line contains N integers Ai (1 ≤ AiM). The input ends with two zeros

Output

For each test case output how many values you can choose for W so that Alice will be the winner without fail.

Sample Input

3 8
1 5 7 
0 0

Sample Output

3

Hint

We say that Alice is surely to win if and only if the possibility that Alice wins is greater than zero and the possibility that Bob wins is zero. For the sample, W = 1, 5, 7.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator