#P6022. 快乐水

快乐水

题目背景

小 W 要去买快乐水。

题目描述

他来到了一家商店门前。

这家商店为了吸引顾客来买快乐水,搞了这么一个活动:「55 个瓶盖换一瓶快乐水」。于是,人们纷纷来他的店里买快乐水。

买完快乐水,他想到了一个问题:

如果一瓶快乐水有 mm 个附属品,对于第 ii 个附属品,每 aia_i 个可以换一瓶全新的快乐水,现在我有买 nn 瓶快乐水的钱,我最多能喝多少快乐水呢?

输入格式

第一行两个整数 n,mn,m,意义如上。

接下来一行 mm 个整数 a1,a2,,ama_1,a_2,\cdots,a_m,意义如上。

输出格式

如果小 W 可以无限白嫖快乐水,那么输出一行一个字符串 Inf

否则,输出一行一个整数 ss,表示小 W 最多能喝的快乐水数量。

5 2
2 4

15
2 2
2 2

Inf

提示

样例一解释:

步数 已喝 未喝 附属品一 附属品二
1 0 5 0
2 5 0 5
3 3 1
4 8 0 4
5 3 0
6 11 0 3 3
7 1
8 12 0 2 4
9 2 0
10 14 0 2 2
11 1 0
12 15 0 1 3

样例二解释:

步数 已喝 未喝 附属品一 附属品二
1 0 2 0
2 2 0 2
3 2 0
4 4 0 2
5 2 0
6 6 0 2
7 2 0
8 0 2
9 \vdots

很显然小 W 可以像这样无限白嫖快乐水。

注意:本题中,我们认为无法借还/赊账。


数据范围:

测试点一与样例二相同。

对于其中 30%30\% 的数据,n100n\le 100m2m\le 2

对于 100%100\% 的数据,1n1041\le n\le 10^41m51\le m\le 51ai2×1031\le a_i\le 2\times10^3