Codeforces 839 B. Game of the Rows-贪心

Daenerys Targaryen has an army consisting of k groups of soldiers, the i-th group contains ai soldiers. She wants to bring her army to the other side of the sea to get the Iron Throne. She has recently bought an airplane to carry her army through the sea. The airplane has nrows, each of them has 8 seats. We call two seats neighbor, if they are in the same row and in seats {1, 2}, {3, 4}, {4, 5}, {5, 6} or {7, 8}.

$\text{[math]}$ A row in the airplane

Daenerys Targaryen wants to place her army in the plane so that there are no two soldiers from different groups sitting on neighboring seats.

Your task is to determine if there is a possible arranging of her army in the airplane such that the condition above is satisfied.

Input

The first line contains two integers n and k (1 ≤ n ≤ 10000, 1 ≤ k ≤ 100) — the number of rows and the number of groups of soldiers, respectively.

The second line contains k integers a1, a2, a3, ..., ak (1 ≤ ai ≤ 10000), where ai denotes the number of soldiers in the i-th group.

It is guaranteed that a1 + a2 + ... + ak ≤ 8·n.

Output

If we can place the soldiers in the airplane print "YES" (without quotes). Otherwise print "NO" (without quotes).

You can choose the case (lower or upper) for each letter arbitrary.

Examples

input

2 2
5 8

output

YES

input

1 2
7 1

output

NO

input

1 2
4 4

output

YES

input

1 4
2 2 1 2

output

YES

Note

In the first sample, Daenerys can place the soldiers like in the figure below:

$\text{[math]}$

In the second sample, there is no way to place the soldiers in the plane since the second group soldier will always have a seat neighboring to someone from the first group.

In the third example Daenerys can place the first group on seats (1, 2, 7, 8), and the second group an all the remaining seats.

In the fourth example she can place the first two groups on seats (1, 2) and (7, 8), the third group on seats (3), and the fourth group on seats (5, 6).

题意:主要的就是不同的军队不能挨着坐。

所以能把4个位置坐满的话就先坐满，然后考虑2个位置的。

对于4个人来说就是坐在中间的4个位置，对于3个人来说也是坐在中间，但是可以有一种操作，把3个人分成2个人和1个人，

然后是考虑2个人和1个人的，都是坐在两边的位置或者中间坐一个2个人坐一个1个人，或者中间坐2个1个人的。

最近太zz了，一开始想的太麻烦了，忘记了还有比较大小这种操作了。。。

代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[1000];
 4 int main(){
 5     int n,k;
 6     while(~scanf("%d%d",&n,&k)){
 7         for(int i=0;i<k;i++)
 8             scanf("%d",&a[i]);
 9         int sum1=n;
10         int sum2=2*n;
11         for(int i=0;i<k;i++){
12             int d=min(sum1,a[i]/4);
13             sum1-=d;
14             a[i]-=d*4;
15         }
16         sum2+=sum1; 
17         for(int i=0;i<k;i++){
18             int d=min(sum2,a[i]/2);
19             sum2-=d;
20             a[i]-=d*2;
21         }
22         int tmp=sum2+sum1;
23         for(int i=0;i<k;i++)
24             tmp-=a[i];
25         if(tmp>=0)printf("YES
");
26         else printf("NO
");
27     }
28     return 0;
29 }