提示: 欢迎访问OurACM平台。
Problem 2096 Merlininice's movies

Accept: 9    Submit: 18
Time Limit: 5000 mSec    Memory Limit : 32768 KB

Problem Description

Merlininice likes watching movies very much! He has lots of movies in his computer. One day, a friend of Merlininice wants to get some movies from him. As Merlininice has so many movies, his friend just wants some of them. To avoid mistakes, Merlininice will select all the needed movies and then send them to his friend together.

Merlininice uses the win7 operation system and four icons can fit in a horizontal row in any window.

The movie folder in Merlininice’s computer contains n movies. These movies are numbered from 1 to n (see the images for example). Merlininice wants to finish selecting by making as few frame selections as possible.

Let us note that if some selected movie is selected repeatedly, then it is deselected. Each frame selection possesses the shape of some rectangle with sides parallel to the screen's borders.

Input

There are several cases. (About 30 large cases and 100 small cases)

For each case, the first input line contains two integers n (1 <= n <= 4000) which represents the number of movies in Merlininice’s computer, and m (1 <= m <= n) which represents the number of movies the friends want.

Then follow a lines contains m numbers which represents the id of movies Merlininice’s friends want.

Output

Output the least possible number of times that Merlininice use the frame selections.

Sample Input

15 11 1 2 3 4 5 8 9 12 13 14 15

Sample Output

2

Hint


Submit  Back  Status  Discuss