Problem J: 开挂的小洋

Problem J: 开挂的小洋

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 250  Solved: 60
Submit Status Web Board

Creator:

Description

最近小洋迷上了一款名叫打地鼠的游戏,但是小洋是个游戏白痴,这么简单的游戏也总是得不到几分,有一天他发现这款游戏可以在网络上买到外挂,这款外挂可以提前预知所有地鼠出现的时间,并且他可以开局得到两把锤子,之前小洋1s只能挥动一次锤子,现在他左右开弓可以同时打中最多两只地鼠。每只地鼠在第i秒出现,在第i+1秒的时候就会消失。也就是说在第i秒小洋只能打到这一秒出现的地鼠,(i-1)秒以及(i+1)秒出现的地鼠他都没办法打中。


Input

一个整数n,表示地鼠的数目
一个整数m,表示此次游戏时长
接下来n个整数a_1-a_n,表示地鼠会在第a_i秒出现
1 <= a_i <= m
1 <= n <= 1000;
1 <= m <= 100000;
每只地鼠最多停留一秒


Output

一个整数,表示小洋最高得分(每打中一只地鼠得一分)

Sample Input

样例输入1:
4
9
1 1 4 7

样例输入2:
6
10
3 3 3 3 9 1

Sample Output

样例输出1:
4

样例输出2:
4

HINT

对于样例1的解释:
第1秒出现两只地鼠 左右开弓两只全打中得2分
第4秒出现一只地鼠 打中得1分
第7秒出现一只地鼠 打中得1分
最终得分4分

对于样例2的解释:
第1秒出现一只地鼠 打中得1分
第3秒出现四只地鼠 两把锤子最多打中两只 得2分
第9秒出现一只地鼠 打中得1分
共4分 



SubmitStatus