← 返回题目列表

Codeforces · 257/A

A. 插座

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

Vasya 有许多依靠电力工作的设备。他有 n 个电源线过滤器来插入设备,第 i 个电源线过滤器有 ai 插座。

总的来说,Vasya 在他的公寓里有 m 个设备和 k 个电源插座,他可以直接插入设备或电源线滤波器。当然,他可以将供应管线过滤器插入任何其他供应管线过滤器。如果该设备(或供电线路过滤器)插入到 k 个电源插座之一,或者插入到某个供电线路过滤器(而该供电线路过滤器又插入了电源),则该设备(或供电线路过滤器)被视为已接通电源。

Vasya 需要给定组中最少数量的供电线路过滤器来为其所有设备供电?请注意,所有设备和电源线过滤器都需要一个插座来插入,并且他可以使用一个插座来插入一台设备或一个电源线过滤器。

输入

第一行包含三个整数 n、m、k (1 ≤ n, m, k ≤ 50) — 相应地,电源线滤波器的数量、设备的数量以及可以直接插入的插座的数量。第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 50) — 数字 ai 代表第 i 个电源线滤波器上的插座数量。

输出

打印一个数字 — 将所有设备通电所需的供电线路过滤器的最小数量。如果即使使用所有电源线过滤器也无法插入所有设备,请打印 -1。

示例

输入 #1

3 5 3
3 1 2

输出 #1

1

输入 #2

4 7 2
3 3 2 4

输出 #2

2

输入 #3

5 5 1
1 3 1 2 1

输出 #3

-1

注意

在第一个测试用例中,他可以将第一个供电线路过滤器直接插入电源。插入后,他会获得 5 个可用插座(其中 3 个在电源线过滤器上,其余 2 个用于直接插入)可用插座进行插入。因此,一个过滤器足以堵塞 5 个设备。

第二个测试样本中的最佳方法之一是直接插入第二个电源线滤波器,并将第四个电源线滤波器插入第二个电源线滤波器中的插座之一。因此,他恰好获得了 7 个可用于插入的插座:1 个用于直接插入电源,2 个用于第二个供电线路过滤器,4 个用于第四个供电线路过滤器。如果他使用一个电源线过滤器,他就不可能插入 7 个设备。