MODIFIED - Bị Biến Đổi
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: ami

Ami có một dãy số A gồm n phần tử, được đánh số từ 1, phần tử thứ i của dãy số được kí hiệu là Ai. Ami có thể thực hiện thao tác sau với số lần bất kỳ : chọn một số Ai mà giá trị hiện tại lớn hơn 1 và trừ số này đi 1 đơn vị. Nếu số Ai đã bị trừ ít nhất một đơn vị, ta gọi số này đã bị biến đổi.

Bây giờ, Ami cần tìm cách thực hiện thao tác sao cho số phần tử bị biến đổi là ít nhất, và tổng các phần từ sau khi thực hiện một số thao tác đúng bằng k.

Input

Dòng đầu tiên chứa 2 số nguyên dương n và k lần lượt là số phần tử, và tổng (n ≤ 105 , k ≤ 1016).

Dòng tiếp theo chứa n số nguyên dương Ai là các phần tử dãy A (Ai ≤ 109).

Output

Một số nguyên là số phần tử ít nhất bị biến đổi. Nếu không tồn tại bất kỳ cách thực hiện thao nào để tổng bằng k, in ra -1

Ví dụ

  • input
    3 4
    1 2 3
    output
    1
  • input
    3 4
    1 2 1
    output
    0
  • input
    3 4
    1 1 1
    output
    -1

Ở test ví dụ 1, có thể chọn phần tử cuối, và trừ đi 1 đơn vị, lặp lại 2 lần, ta có dãy sau 1 2 1. Dãy số có tổng đúng bằng 4, và chỉ thực hiện thao tác lên phần tử cuối, do đó kết quả là 1.

Ở test ví dụ 2, vì dãy số đã có tổng bằng k, không có phần tử bị biến đổi, nên kết quả là 0.

Ở test ví dụ 3, không tồn tại cách biến đổi để dãy số có tổng bằng k. In ra -1.

Back to Top