Tấn công diện rộng (Widespread)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ quái vật, quái vật thứ $i$ có $h_i$ máu.

Mỗi lần gây nổ, chọn một quái vật còn sống làm tâm. Quái vật ở tâm mất $A$ máu; mỗi quái vật còn sống khác mất $B$ máu, với $A>B$.

Quái vật biến mất ngay khi máu không còn dương. Hãy tìm số vụ nổ ít nhất cần thực hiện để tiêu diệt tất cả quái vật.

Input

Dòng đầu chứa $N,A,B$. $N$ dòng tiếp theo lần lượt chứa $h_i$.

Output

In số vụ nổ nhỏ nhất.

Subtask

• Subtask 1 — 20%: $N=1$.
• Subtask 2 — 30%: $1\le N\le1000$.
• Subtask 3 — 50%: $1\le N\le10^5$, $1\le B<A\le10^9$, $1\le h_i\le10^9$.

Ví dụ

Input

4 5 3
8
7
4
2

Output

2

Giải thích

Ban đầu máu của bốn quái vật là $8,7,4,2$.

• Gây vụ nổ thứ nhất tại quái vật có $8$ máu. Máu còn lại trở thành $3,4,1,-1$; quái vật cuối biến mất.
• Gây vụ nổ thứ hai tại quái vật đang có $4$ máu. Ba quái vật còn lại trở thành $0,-1,-2$ và đều biến mất.

Vậy $2$ vụ nổ là đủ. Một vụ nổ không thể tiêu diệt cả bốn quái vật, nên đáp án là $2$.