Bạn muốn lấy kho báu nằm ở tầng ngầm thứ \(N\) của một hầm ngục. Ban đầu, bạn đang ở tầng ngầm thứ \(1\) và có \(H\) thể lực, trong đó \(H\) là số nguyên dương. Mỗi lần xuống tầng bên dưới, bạn sẽ tiêu hao thể lực. Lượng thể lực tiêu hao khi đi xuống từ mỗi tầng đã được biết trước.

Mỗi tầng có một suối hồi phục. Lượng thể lực hồi phục sau mỗi lần sử dụng suối được xác định riêng cho từng tầng. Nếu thể lực giảm xuống \(0\) hoặc thấp hơn, bạn sẽ chết. Thể lực cũng không bao giờ vượt quá \(H\), kể cả khi hồi phục. Bạn có thể sử dụng suối bao nhiêu lần tùy ý, nhưng việc hồi phục mất thời gian, nên bạn muốn dùng suối ít lần nhất có thể.

Một khi đã xuống tầng bên dưới, bạn không thể quay lại tầng phía trên cho đến khi lấy được kho báu.

Yêu cầu

Cho \(N\), \(H\), lượng thể lực tiêu hao khi đi xuống từ mỗi tầng và lượng thể lực hồi phục sau mỗi lần sử dụng suối ở từng tầng, hãy viết chương trình tính số lần sử dụng suối ít nhất cần thiết để đến tầng ngầm thứ \(N\) mà không để thể lực giảm xuống \(0\) hoặc thấp hơn.

Dữ liệu vào

Dữ liệu được cung cấp qua đầu vào chuẩn, gồm \(N\) dòng.

• Dòng đầu tiên chứa hai số nguyên \(N,H\), cách nhau bởi dấu cách. Kho báu nằm ở tầng ngầm thứ \(N\); \(H\) vừa là thể lực ban đầu khi bạn đến tầng ngầm thứ \(1\), vừa là thể lực tối đa.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách. Dòng thứ \(i+1\) (\(1\le i\le N-1\)) chứa \(d_i,h_i\): \(d_i\) là thể lực tiêu hao khi đi từ tầng ngầm thứ \(i\) xuống tầng ngầm thứ \(i+1\), còn \(h_i\) là thể lực hồi phục sau mỗi lần sử dụng suối tại tầng ngầm thứ \(i\). Việc hồi phục không thể làm thể lực vượt quá \(H\).

Mọi dữ liệu chấm đều bảo đảm có cách đến được tầng ngầm thứ \(N\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số lần sử dụng suối ít nhất cần thiết để đến tầng ngầm thứ \(N\) mà không để thể lực giảm xuống \(0\) hoặc thấp hơn.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
• \(2\le N\le100000=10^5\).
• \(1\le H\le10000000=10^7\).
• \(0\le d_i<H\) (\(1\le i\le N-1\)).
• \(1\le h_i<H\) (\(1\le i\le N-1\)).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.
• Luôn tồn tại cách đến tầng ngầm thứ \(N\).

Phân nhóm

Bài này có tổng cộng \(20\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm. Các tỷ lệ dưới đây được tính trên tổng điểm của bài.

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le1000\) và \(H\le1000\).
• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le1000\).
• \(50\%\) số điểm dành cho các dữ liệu mà số lần sử dụng suối ít nhất không vượt quá \(10^6\).

Lưu ý

Các số nguyên cần xử lý trong bài này có thể vượt quá phạm vi biểu diễn của số nguyên 32 bit.

Ví dụ

10 10
4 2
2 5
6 1
7 3
6 4
9 6
0 8
4 1
9 4

10