Sắp xếp kiện hàng

Tại một bến cảng có $n$ kiện hàng cần được xếp xuống tàu để vận chuyển. Các kiện hàng được đánh số thứ tự từ 1 đến $n$ theo thứ tự nó được gởi đến kho hàng, kiện hàng thứ $i$ có khối lượng $a_i$. Người ta lần lượt xếp từng kiện hàng theo thứ tự từ kiện hàng thứ nhất, đến kiện hàng thứ hai, ... cho đến khi không thể xếp được nữa. Biết rằng tàu hàng có tải trọng là $M$ và các kiện hàng xếp xuống tàu không được vượt quá tải trọng của nó. Những kiện hàng không xếp được phải để lại cảng chờ chuyến tàu tiếp theo.

Do yêu cầu đặc biệt, kiện hàng thứ $k$ cần phải được vận chuyển trong thời gian sớm nhất, vì vậy ban quản lý cảng quyết định chọn một số kiện hàng để lại cảng (thay vì được xếp lên chuyến tàu này) nhường chỗ cho kiện hàng $k$ được ưu tiên xếp xuống tàu.

Yêu cầu: Hãy cho biết ban quản lý cảng phải chọn ít nhất bao nhiêu kiện hàng để lại cảng thay vì chúng được xếp lên tàu để nhường chỗ cho kiện hàng $k$?

Cho từ tệp văn bản KIENHANG.INP gồm hai dòng:

• Dòng thứ nhất ghi ba số nguyên dương $n$, $M$, $k$ ($1 \le k \le n \le 10^5$, $1 \le M \le 10^9$).
• Dòng thứ hai ghi $n$ số nguyên dương $a_1, a_2, \dots, a_n$ ($1 \le a_i \le M$, $i = 1..n$).

Ghi vào tệp văn bản KIENHANG.OUT gồm một dòng ghi một số nguyên là số kiện hàng ít nhất phải để lại cảng thay vì chúng được xếp lên tàu để nhường chỗ cho kiện hàng $k$.

• Có 70% số test tương ứng 70% số điểm có $n \le 10^3$.
• Có 30% số test tương ứng 30% số điểm có $n \le 10^5$.