LUYỆN TẬP DỰ THI OLYMPICNĂM 2011 ĐÁNH DẤU 20 NĂM HÌNH THÀNH VÀ...

Bài 3. Luyện tập dự thi OlympicNăm 2011 đánh dấu 20 năm hình thành và phát triển của Olympic Tin học sinh viên Việt Nam. Để hỗ trợ các bạn sinh viên chuẩn bị tốt cho kỳ thi này, trên website IT-2011 có n bài tập (1 ≤ n ≤ 10

⁵

). Các bài được đánh số từ 1 đến n. Mỗi bài tập nhằm rèn luyện một số kỹ năng cho thí sinh, ví dụ như kỹ thuật lập trình, giải thuật, cấu trúc dữ liệu… Nhằm định hướng cho quá trình tự luyện tập được hiệu quả, mỗi bài tập có một yêu cầu tối thiểu về trình độ kỹ năng. Để giải được bài thứ i, bạn cần có trình độ kỹ năng tối thiểu là a

i

. Điều này có nghĩa là sinh viên có thể giải được bài thứ i khi và chỉ khi có trình độ kỹ năng bằng hoặc lớn hơn a

i

. Nếu giải được bài thứ i trình độ kỹ năng của sinh viên sẽ tăng thêm một lượng là b

i

(1 ≤ a

i

, b

i

≤ 10

⁹

). Giả sử ban đầu, trình độ kỹ năng của bạn trước khi làm bài tập là c (0 ≤ c ≤ 10

⁹

). Các bài tập có thể được làm theo trình tự bất kỳ tùy chọn.Ví dụ, với trình độ kỹ năng ban đầu c = 1, n = 4 và các giá trị a

i

, b

i

tương ứng là (1, 10), (21, 5), (1, 10), (100, 100), bạn sẽ giải bài 1, sau đó làm bài 3 và cuối cùng làm bài 2. Như vậy bạn sẽ làm được tất cả là 3 bài.Yêu cầu: Cho các số nguyên n, c và các cặp giá trị (a

i

, b

i

), 1 ≤ i ≤ n. Hãy xác định số lượng bài tối đa có thể được giải.Dữ liệu: Vào từ file văn bản OLYMPIC.INP có cấu trúc như sau:

•

Dòng đầu tiên chứa 2 số nguyên n và c,

•

Dòng thứ i trong n dòng tiếp theo (1 ≤ i ≤ n) chứa 2 số nguyên a

i

và b

i

.Các số trên cùng một dòng được ghi cách nhau bởi 1 khoảng trắng.Kết quả: Đưa ra file văn bản OLYMPIC.OUT một số nguyên – số lượng bài tối đa có thể được giải.Ví dụ: OLYMPIC.INP OLYMPIC.OUT4 131 1021 5100 100