socks

Problem Description

Crud! Damian is late for a scouts camp but has yet to pack his socks. As he likes to wear matching socks, he needs K socks of the same kind. However, his socks (of N different kinds) are all in a jumble so he decides to just grab a handful of them.

Furthermore, he knows that he has Ai socks of type i.

How many socks does he need to grab to guarantee that he will have at least K socks of one kind?

Input

The first line contains two integers, N and K.

The second line contains N space-separated integers, representing the contents of A.

Output

A single integer representing the minimum number of socks that Damian has to grab. If it is not possible for Damian to guarantee at least K socks, output -1 instead.

Subtasks

  • Subtask 1 (30%): 1 ≤ N ≤ 100; 0 ≤ K ≤ Ai ≤ 1000.
  • Subtask 2 (70%): 1 ≤ N ≤ 100; 0 ≤ Ai ≤ 1000; 0 ≤ K ≤ 1000.
  • Subtask 3 (0%): Sample Testcase.

Sample Input

3 4
5 5 5

Sample Output

10
Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 20
Your best score: 0
Source: December Course 2018 Elementary Final Contest (Damian)

Subtask Score
1 30
2 70
3 0