---
# System prepended metadata

title: Bài 3. Tên lửa hạt nhân

---

# Bài 3. Tên lửa hạt nhân

Author: **kimjongun**

Dạng bài: Mảng (Array)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256MB

---

Triều Tiên sắp thử bắn loại tên lửa hạt nhân mới mà họ mới vừa sản xuất, HN02.
Trong kho vũ khí bây giờ của họ đang có $N$ tên lửa HN02, tên lửa thứ $i$ có sức bay xa là $A_i$. Họ có thể lắp một tên lửa phía sau đuôi của một tên lửa khác, và khi tên lửa phía trước hết sức bay, nó sẽ tự đẩy tên lửa được phía sau đuôi của nó ra, và tên lửa này sẽ bay tiếp. Một tên lửa có thể gắn vô số chiếc tên lửa khác và nguyên tắc là tên lửa có sức bay gần hơn sẽ được gắn vào tên lửa có sức bay xa hơn.
**Ví dụ đơn giản:**
![](https://i.imgur.com/1QQ8QsA.png)
> **Ở ví dụ trên bạn có thể thấy:**
Ở đầu bên trái, có tên lửa bay 5km gắn vào tên lửa bay 10km. Khi bay được 10km thì tên lửa thứ nhất rơi xuống (hết sức bay), tên lửa thứ hai rời ra khỏi tên lửa thứ nhất, và bay tiếp đến bờ bên phải.

**Yêu cầu:** Vậy giả sử bờ bên trái là đất nước Triều Tiên, còn bờ bên phải là mục tiêu của họ nhắm bắn (một quốc gia nào đó). Hỏi phải chọn ít nhất bao nhiêu tên lửa để đủ bay từ bờ bên trái sang bờ bên phải ? Dữ liệu đảm bảo rằng tên lửa sẽ rơi trúng đích (không thiếu cũng không thừa).

**Dữ liệu vào:**
- Dòng đầu ghi số nguyên dương $N$ không quá $10^6$, là số lượng tên lửa mà Triều Tiên đang có trong kho.
- Dòng tiếp theo ghi ra $N$ số nguyên dương ($A_i <10^7+1$) thể hiện cho sức bay của tên lửa thứ $i$.
- Dòng thứ ba ghi số $V$ là khoảng cách giữa đầu bên trái & đầu bên phải.

**Dữ liệu xuất:**
- Gồm 1 số duy nhất là số lượng tên lửa ít nhất để bay từ đầu bên trái sang đầu bên phải. Dữ liệu đảm bảo chỉ có 1 cách duy nhất.

**Sample Input:**

---
```
7
2 6 4 5 10 8
15
```

**Sample Output**

---
```
2
```
**Giải thích**: Có 2 tên lửa có độ bay là $5$ và $10$ đáp ứng yêu cầu.
> Từ contest: Ôn luyện thi cấp Quận
> Contest Author: **kimjongun**