| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P136SUMF - SUM6 F - Mạng lưới điện thoại |
Sau khi tốt nghiệp đại học ngành viễn thông, đang trong lúc rảnh rỗi chờ việc làm, Tồ ở nhà chán không biết làm gì nên nghĩ ra trò nghe trộm điện thoại. Ngôi làng của Tồ có M hộ gia đình sống dọc theo ven sông, được đánh số từ 1 tới M.
Ngôi làng này mới được nâng cấp hệ thống đường dây điện thoại, tuy nhiên Tồ đã chế ra được thiết bị nghe trộm điện thoại trên hệ thống này. Thiết bị này có thể nghe trộm được cuộc gọi giữa 2 ngôi nhà, nếu như nó được lắp đặt nằm giữa 2 ngôi nhà này.
Bài toán đặt ra là cho vị trí thiết bị và tổng số cuộc gọi được phát hiện bởi từng thiết bị mà Tồ sử dụng, hãy tính số lượng cuộc gọi tối thiểu được thực hiện.
Input
Dòng đầu tiên gồm hai số nguyên n - số thiết bị mà Tồ sử dụng, và m là số ngôi nhà trong làng, (1 ≤ n ≤ 100 000, n < m ≤ 10^9).
N dòng tiếp theo, mỗi dòng gồm 2 số p_i và c_i mô tả vị trí và tổng số cuộc gọi được phát hiện bởi thiết bị thứ i. Ta nói một thiết bị được đặt ở vị trí p_i nếu và chỉ nếu nó nằm giữa hai ngôi nhà có số thứ tự p_i và p_(i+1), (1 ≤ p_i < m, 1 ≤ c_i ≤ 10^9).
Không có hai thiết bị được đặt cùng một vị trí.
Output
In ra một số nguyên duy nhất là số cuộc gọi tối thiểu được thực hiện.
Example
Test 1:
Input:
3 4
3 1
2 2
1 1
Output:
2
Test 2:
Input:
2 3
1 23
2 17
Output:
23
Test 3:
Input:
3 9
7 2
8 3
3 4
Output:
5
| Được gửi lên bởi: | adm |
| Ngày: | 2013-08-25 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
