欢乐聚会

背景描述:
学校组织了一场盛大的聚会,大家围着圈,跳起了舞!Will当然也参加啦!
不过现在这个世道,一个字——乱啊!连学校里都是学生成天拉帮结派的,据Will的死党QL提供的消息,学校里至少有K个帮派,每个学生都属于一个帮派。
帮派是一个很有意思的东西,经过Will的观察,可以将帮派编号,存在唯一的一种标号方法使得这些帮派标为了1~N号,更有意思的是,1号帮派从属于2号帮派,2号帮派从属于3号帮派,3号帮派从属于4号帮派……而且,N号帮派从属于1号帮派
因为帮派的从属关系,从属帮派的同志们一定紧紧跟随着他的上司帮派成员,跳舞的时候也是这样(唉……怎么这么黑暗……)。
现在大家围成了一些圈,每一个圈内的学生的序列都满足从属关系。
这是一个盛大的聚会,因此大家围成了好多圈跳舞,好奇的Will想知道,这里面最少可能有和最多可能有多少个帮派呢?

问题:
给定N,现在同学们围成的圆圈数量,和每个圆圈的人数 a[1..N],QL的调查信息 K。求出最少和最多可能的帮派。如果发现QL的调查信息有误,那么只要输出两个-1 就可以了。

输入:
第一行,两个整数 N, K
第二行,N个整数 a[1..N]

输出:
一行两个整数,最小的帮派可能,和最多的帮派可能。

注意:先输出最小的可能,再输出最大的可能。

样例1:
[party.in]
3 3
6 9 12

[party.out]
3 3

样例2:
[party.in]
3 5
4 8 16

[party.out]
-1 -1

Hint:
在样例2中,出现了4个人组成的环,那么帮派总数不可能超过4,因此QL提供的消息是错误的。

数据规模:
对于30%的数据 N ≤ 1000 a[i] ≤ 1000
对于100%的数据 N ≤ 100000 a[i] ≤ 10000000 2 ≤ K ≤ 200

信息

ID
1870
难度
10
分类
(无)
标签
递交数
2
已通过
0
通过率
0%
被复制
2
上传者