← 返回题目列表

Codeforces · 149/A

A. 出差

中文机器翻译题面 查看原题

多么高兴!佩蒂亚的父母一整年都在出差,只剩下这个顽皮的孩子独自一人。佩蒂亚非常高兴。他整天在床上跳来跳去,扔枕头,直到……

今天 Petya 打开柜子,发现里面有一张可怕的纸条。他的父母给他留下了一些义务:他必须全年每天早上、下午和晚上给他们最喜欢的花浇水。 “等一下!” ——彼佳想。他知道一个事实,如果他在一年中的第 i (1 ≤ i ≤ 12) 个月完成了父母的任务,那么这朵花就会长 ai 厘米,如果他在第 i 个月不给这朵花浇水,那么这个月这朵花就不会生长。 Petya 也知道,无论他如何努力,如果花的生长严格小于 k 厘米,他的父母都不会相信他一直在给花浇水。

帮助 Petya 选择浇花的最少月数,前提是花的生长长度应不少于 k 厘米。

输入

第一行恰好包含一个整数 k (0 ≤ k ≤ 100)。下一行包含 12 个以空格分隔的整数:该行中的第 i 个 (1 ≤ i ≤ 12) 数字表示 ai (0 ≤ ai ≤ 100)。

输出

打印唯一的整数 - Petya 必须给花浇水以使花长得不少于 k 厘米的最小月数。如果花一年内不能增长 k 厘米,则打印 -1。

示例

输入 #1

5
1 1 1 1 2 2 3 2 2 1 1 1

输出 #1

2

输入 #2

0
0 0 0 0 0 0 0 1 1 2 3 0

输出 #2

0

输入 #3

11
1 1 4 1 1 5 1 1 4 1 1 1

输出 #3

3

注意

让我们考虑第一个示例测试。在那里,第七个月和第九个月浇花就足够了。然后花就长了五厘米。

在第二个样本中,即使花根本不生长(k = 0),Petya 的父母也会相信他。因此,Petya 有可能根本不给花浇水。