Nguồn: Bài tập thầy Nguyễn Thanh Bình Ôn ĐT Hải Phòng T10/2020
Trong khu đô thị mới của thành phố chỉ có hai loại đường ngang và dọc. Để đơn giản ta có thể mô tả hệ thống giao thông này trên mặt phẳng hai chiều, các đường ngang theo hướng Tây - Đông được đánh số từ trên xuống dưới, các đường dọc theo hướng Bắc - Nam được đánh số từ trái sang phải (chú ý là các con đường này đều đi lại được theo hai hướng). Giao điểm của các đường ngang và dọc là các ngã rẽ. Ngã rẽ ký hiệu là giao của đường ngang và đường dọc .
Công ty tin học ABC có trụ sở đặt tại (giao của đường ngang và đường dọc ). Hàng ngày công ty có một số ô tô chở nhân viên đi làm. Tất cả các ô tô này đều xuất phát từ vị trí , đi theo các tuyến đường ngang và dọc đến . Một điều thú vị là hành trình của các xe ô tô có thể khác nhau nhưng luôn là hành trình có tổng độ dài ngắn nhất từ đến . Có ngã rẽ, đánh số là điểm dừng đón nhân viên của các ô tô. Hàng ngày tại ngã rẽ thứ có nhân viên của công ty đứng đón ô tô đi làm.
Yêu cầu: Tính số lượng nhiều nhất các nhân viên của công ty mà ô tô đầu tiên trong ngày có thể đón với giả thiết số chỗ ngồi trên xe đủ để đón tất cả các nhân viên công ty trong một lượt chạy.
Dữ liệu vào:
Dòng đầu tiên chứa ba số nguyên dương ;
dòng tiếp theo, dòng thứ chứa ba số nguyên dương thể hiện là vị trí ngã rẽ đón khách thứ i còn là số lượng nhân viên công ty đứng đợi ở ngã rẽ này .
Các số nguyên liên tiếp trên cùng một dòng cách nhau ít nhất một khoảng trống.
Dữ liệu ra:
Một số nguyên duy nhất là số lượng nhân viên lớn nhất có thể lên ô tô trong chuyến đầu tiên.
Giới hạn:
Subtask số điểm của bài có ;
Subtask số điểm khác có ;
Subtask số điểm khác có ;
Subtask số điểm còn lại không có ràng buộc bổ sung.
