Con Bò Đói

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie là một con bò ăn đúng một bó cỏ mỗi ngày (vào buổi tối) nếu kho còn cỏ. Nông dân John giao cỏ vào những ngày nhất định. Vào sáng ngày $d_{i}$ , một đợt giao $b_{i}$ bó cỏ được đưa đến kho (trước bữa tối).

Hãy tính tổng số bó cỏ Bessie ăn trong $T$ ngày đầu tiên.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $T$ ( $1 \leq N \leq 10^{5}$ , $1 \leq T \leq 10^{14}$ ) — số đợt giao và số ngày.
$N$ dòng tiếp theo: Mỗi dòng chứa hai số nguyên $d_{i}$ và $b_{i}$ ( $1 \leq d_{i} \leq T$ , $1 \leq b_{i} \leq 10^{9}$ ) — ngày giao và số bó cỏ. Các ngày giao tăng dần ( $d_{1} < d_{2} < \dots < d_{N}$ ).

Dữ liệu ra

Một số nguyên duy nhất — tổng số bó cỏ Bessie đã ăn trong $T$ ngày đầu tiên.

Ràng buộc

$1 \leq N \leq 10^{5}$
$1 \leq T \leq 10^{14}$
$1 \leq d_{1} < d_{2} < \dots < d_{N} \leq T$
$1 \leq b_{i} \leq 10^{9}$
Sử dụng số nguyên 64-bit.

Ví dụ

Input	Output	Giải thích
1 5 1 2	2	Ngày 1 giao 2 bó. Bessie ăn ngày 1 và ngày 2. Hết cỏ từ ngày 3.
2 5 1 2 5 10	3	Ngày 1 giao 2 bó (ăn ngày 1, 2). Ngày 5 giao 10 bó (ăn ngày 5). Tổng 3.
2 5 1 10 5 10	5	Kho luôn có cỏ nên Bessie ăn đủ cả 5 ngày.

Bình luận

Không có bình luận tại thời điểm này.