Description

当地的文具店卖一种颜料盒，每盒有N个装有不同颜色颜料的瓶子，每个瓶子都为50ml。3种Xml的不同颜色颜料倒在一起可以得到Xml的灰色颜料，买来的颜料盒中并没有灰色，唯一得到灰色的方法就是用已有的颜料去混合得到，至于是哪3种颜料混合得到的灰色颜料都是一样的。 现在需要不同颜色的需求量和灰色的需求量，求最少需要买几盒颜料盒。

Input

输入包含多组数据，以0结束输入。 每组数据包含5个或以上的整数，以空格隔开。第一个整数N是颜料盒中的颜色数目（3 ≤ N ≤ 12），接下来是N个非负整数，不超过1000，表示每种颜色的需求量，最后一个非负数是灰色的需求量。

Output

针对每组数据输出最少需要买的颜料盒数。

Sample

Input

3 40 95 21 0
7 25 60 400 250 0 60 0 500
4 90 95 75 95 10
4 90 95 75 95 11
5 0 0 0 0 0 333
0

Output

2
8
2
3
4