Description

DK小朋友平时很喜欢看漫画，有一次跟他妈妈去逛街，看见一家专卖漫画的书店。里面的漫画都是DK小朋友喜欢的类型，所以他缠着妈妈想要买下所有的书，但是妈妈钱带的不多，不可能买下所有DK喜欢的书，可是每个妈妈都想要自己的孩子开心，所以她打算有身上所有的钱去买尽可能多的书给DK。

Input

有多组测试数据。 每组测试数据的第一行为两个整数tot和n，分别表示妈妈身上所有的钱和书店里书的本数。 接下来的一行有n个整数，分别表示每本书的价格。

Output

对于每组册书数据都输出DK最多能得到几本书。

Sample

Input

100 3
56 23 68
2 2
2 3

Output

2
1

Source: z_y