USACO 2023 February Contest, Bronze, Hungry Cow
Xem PDFBessie là một cô bò rất hay đói bụng. Mỗi ngày, vào giờ ăn tối, nếu có cỏ khô trong chuồng, nó sẽ ăn một bó. Để Bessie không bị đói, bác nông dân John thỉnh thoảng sẽ mang cỏ khô đến vào buổi sáng (trước bữa tối). Cụ thể, vào ngày \(dᵢ\), bác John gửi \(b_i\) kiện cỏ khô \((1 \le d_i \le 10^{14}, 1 \le b_i \le 10^9)\).
Tính tổng số bó cỏ khô mà Bessie sẽ ăn trong \(T\) ngày đầu tiên.
INPUT
Nhập dữ liệu từ terminal/stdin:
- Dòng đầu tiên chứa \(N\) và \(T\) \((1 \le N \le 10^5, 1 \le T \le 10^{14})\).
- \(N\) dòng tiếp theo, mỗi dòng chứa \(d_i\) và \(b_i\). Đảm bảo rằng 1 < \(d_1\) < \(d_2\) < ... < \(d_n\) ≤ \(T\).
OUTPUT
In ra terminal/stdout:
- In ra số lượng kiện cỏ khô mà Bessie sẽ ăn trong \(T\) ngày đầu tiên.
Note: Vì các số trong bài toán có thể rất lớn, bạn nên sử dụng kiểu dữ liệu số nguyên 64 bit (ví dụ: long long trong C/C++).
SCORING
- Input \(4 - 7\): \(T \le 10^5\)
- Input \(8 - 13\): Không có ràng buộc gì thêm
Test 1
Input
1 5
1 2
Output
2
Note
Vào buổi sáng ngày \(1\), \(2\) bó cỏ khô được mang đến. Bessie ăn một bó vào bữa tối ngày \(1\) và bó còn lại vào ngày \(2\). Từ ngày \(3\) đến ngày \(5\), Bessie không có cỏ khô để ăn. Do đó, trong 5 ngày đầu tiên, Bessie đã ăn tổng cộng 2 kiện cỏ khô.
Test 2
Input
2 5
1 2
5 10
Output
3
Note
Vào buổi sáng ngày \(1\), \(2\) bó cỏ khô được mang đến. Bessie ăn \(1\) kiện vào ngày \(1\) và \(1\) bó vào ngày \(2\). Trong ngày \(3\) và ngày \(4\), Bessie không có cỏ khô để ăn. Đến sáng ngày \(5\), có thêm \(10\) bó cỏ khô được mang đến, và Bessie ăn một bó vào bữa tối ngày \(5\). Vậy tổng cộng, Bessie đã ăn \(3\) bó cỏ khô trong \(5\) ngày đầu tiên.
Test 3
Input
2 5
1 10
5 10
Output
5
Note
\(10\) bó cỏ khô được gửi vào buổi sáng ngày \(1\). Bessie ăn \(1\) bó cỏ khô từ ngày \(1\) đến ngày \(4\). Vào ngày thứ \(5\), có thêm \(10\) bó cỏ khô nữa được gửi tới, lúc này có \(16\) bó cỏ khô trong chuồng. Bessie tiếp tục ăn \(1\) bó vào bữa tối ngày \(5\). Như vậy, trong \(5\) ngày đầu tiên, Bessie đã ăn tổng cộng \(5\) bó cỏ khô.
Bình luận