Bài tập

Minh và Bảo đang du lịch tại nước Pháp. Ở đây có \(n\) thành phố, tất cả nằm dọc theo một con đường cao tốc. Các thành phố được đánh số liên tiếp từ 1 đến \(n\). Khoảng cách từ thành phố \(i\) đến vị trí bắt đầu con đường là \(D_i\).

Minh đang ở thành phố \(u\), Bảo ở thành phố \(v\). Hai bạn muốn tìm một thành phố \(k\) để gặp nhau sao cho \(max(|D_k - D_u|,|D_k - D_v|)\) là nhỏ nhất.

Yêu cầu: Cho \(n\) và \(q\) hãy tìm giá trị nhỏ nhất như yêu cầu ở trên.

Input

• Dòng đầu tiên chứa lần lượt hai số nguyên dương \(n, q\);
• Dòng thứ hai chứa dãy \(D_1, D_2, \dots, D_n\) \((1 \leq D_i \leq 10^9)\);
• Dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) mô tả một câu hỏi.

Output

Ghi ra \(q\) dòng lần lượt là đáp án cho \(q\) câu hỏi.

Example

5 2
1 2 3 4 5
1 5
2 3

2
1

Scoring

• Subtask \(1\) (\(40\%\) số điểm) : \(n, q \leq 10^2\).
• Subtask \(2\) (\(30\%\) số điểm) : \(n, q \leq 10^5\) và $d_1 < d_2 < \cdots < d_n $.
• Subtask \(2\) (\(30\%\) số điểm) : \(n, q \leq 10^5\).

Quanlt206 là một người chủ trang trại có một đàn mèo cực kỳ đáng yêu! Anh ta nuôi \(m\) chú mèo và thuê \(p\) người cho ăn. Có một con đường thẳng chạy xuyên qua trang trại với \(n\) ngọn đồi nằm dọc theo con đường, đánh số từ 1 đến \(n\) từ trái qua phải. Khoảng cách giữa ngọn đồi \(i\) và \((i - 1)\) là \(d_i\) mét. Các người cho ăn đều sống tại ngọn đồi 1.

Vào một ngày đẹp trời, các chú mèo quyết định đi dạo chơi. Chú mèo \(i\) đi đến ngọn đồi \(h_i\), kết thúc chuyến đi vào thời điểm \(t_i\), và sau đó ngồi chờ ở đó để được một người cho ăn đón về. Các người cho ăn phải đón hết tất cả các chú mèo. Mỗi người cho ăn sẽ đi thẳng từ ngọn đồi 1 đến ngọn đồi \(n\) mà không dừng lại, và đón tất cả các chú mèo đang chờ đợi tại mỗi ngọn đồi mà họ đi qua. Tất cả người cho ăn đều di chuyển với tốc độ 1 mét mỗi đơn vị thời gian và có thể đón được bất kỳ số lượng mèo nào mà không gặp khó khăn.

Ví dụ minh họa: Giả sử có hai ngọn đồi \((d_2 = 1)\) và một chú mèo đã kết thúc chuyến đi tại thời điểm 3 ở ngọn đồi 2 \((h_1 = 2)\). Khi đó, nếu người cho ăn rời ngọn đồi 1 vào thời điểm 2 hoặc 3, anh ta có thể đón chú mèo này. Nhưng nếu người cho ăn rời ngọn đồi 1 tại thời điểm 1, chú mèo sẽ không được đón kịp. Nếu người cho ăn rời ngọn đồi 1 tại thời điểm 2, chú mèo phải chờ 0 đơn vị thời gian; nếu người cho ăn rời ngọn đồi 1 tại thời điểm 3, chú mèo phải chờ thêm 1 đơn vị thời gian.

Nhiệm vụ của bạn: Hãy lập kế hoạch cho từng người cho ăn xuất phát từ ngọn đồi 1 sao cho tổng thời gian chờ đợi của tất cả các chú mèo là nhỏ nhất.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\), \(p\) \((2 \leq n \leq 10^5, 1 \leq m \leq 10^5, 1 \leq p \leq 100)\) --- số lượng ngọn đồi, số lượng mèo, và số lượng người cho ăn.
• Dòng thứ hai chứa \(n - 1\) số nguyên \(d_2, d_3, \ldots, d_n\) \((1 \leq d_i \leq 10^4)\) --- khoảng cách giữa các ngọn đồi liên tiếp.
• Mỗi dòng trong \(m\) dòng tiếp theo chứa hai số nguyên \(h_i\) và \(t_i\) \((1 \leq h_i \leq n, 0 \leq t_i \leq 10^9)\) --- vị trí ngọn đồi và thời điểm chú mèo \(i\) kết thúc chuyến đi.

Output

In ra một số nguyên duy nhất --- tổng thời gian chờ đợi nhỏ nhất có thể của tất cả các chú mèo.

Example

4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12

3

Scoring

• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(p = 1\).

• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(m \leq 10\).

• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(m \leq 500, h_{i} = h_{i + 1}\).

• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(m \leq 500\).

• \(20\%\) số test tương ứng với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

Ban hậu cần của CLB CHTcoder cần gửi gấp một lô máy chủ (server) chấm bài từ Hà Nội vào Hồ Chí
Minh để phục vụ kỳ thi sắp tới. Tuy nhiên, hệ thống vận tải đối tác lại không có chuyến xe chạy thẳng.
Mọi lộ trình đều phải trung chuyển qua Huế, nơi các xe tiếp tục nối chuyến để đi vào phía Nam.

Hiện tại có các chuyến xe như sau:

• \(N\) chuyến từ Hà Nội đến Huế, xuất phát tại các thời điểm \(a_i\), mỗi chuyến mất đúng \(T_a\) thời gian.
• \(M\) chuyến từ Huế đến Hồ Chí Minh, xuất phát tại các thời điểm \(b_j\), mỗi chuyến mất đúng \(T_b\) thời gian.

Lô máy chủ chỉ có thể nối chuyến nếu xe từ Huế khởi hành không sớm hơn thời điểm hàng đến nơi: $\(b_j \ge a_i + T_a.\)$

Bộ phận kỹ thuật phát hiện server chưa được cài đặt xong môi trường, nên người quản lý muốn lô
hàng không thể đến được nơi nhận để giữ lại kho sửa lỗi. Nếu bắt buộc phải chuyển đi (luôn tồn tại
cách nối chuyến), thì hàng phải đến muộn nhất có thể để team kỹ thuật có thêm thời gian thao tác
từ xa. Người quản lý được phép hủy tối đa \(K\) chuyến vận chuyển trong tất cả \(N + M\) chuyến để thực
hiện mục đích này.

Em hãy xác định thời điểm lô máy chủ đến Hồ Chí Minh trong trường hợp xấu nhất (đến muộn
nhất) hoặc thông báo hàng không thể đến được nơi nhận.

Input

Đọc từ file văn bản VANCHUYEN.INP:

• Dòng đầu gồm 5 số nguyên dương \(N, M, T_a, T_b, K\) (\(1 \le N, M \le 10^6\), \(1 \le T_a, T_b \le 10^9\), \(0 \le K \le N + M\)).
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(1 \le a_1 < a_2 < \cdots < a_N \le 10^9\)).
• Dòng thứ ba gồm \(M\) số nguyên dương \(b_1, b_2, \ldots, b_M\) (\(1 \le b_1 < b_2 < \cdots < b_M \le 10^9\)).

Output

Ghi ra file văn bản VANCHUYEN.OUT:

• Một số nguyên là thời điểm đến nơi nhận muộn nhất có thể. Nếu hàng không thể đến nơi được thì ghi -1.

Example

4 5 1 1 2
1 3 5 7
1 2 3 9 10

11

Scoring

• 60% số test đầu tiên ứng với 60% số điểm có \(N, M \le 2000\).
• 40% số test còn lại ứng với 40% số điểm có \(N, M \le 10^6\).

Trong thế giới công nghệ, Minh là một kỹ sư máy tính đang cần mua một bộ vi xử lý và một card đồ họa để lắp ráp cỗ máy server cá nhân. Nơi anh sống có \(n\) cửa hàng chuyên bán linh kiện, được đánh số từ \(1\) đến \(n\). Tại mỗi cửa hàng \(i\), bộ vi xử lý có giá \(c_i\) đồng. Card đồ họa có thể được tìm thấy ở bất kỳ đâu, nhưng Minh sẽ mua nó sau khi đã có vi xử lý.

Hệ thống giao thông công cộng chủ yếu ở đây là tàu điện ngầm. Có \(m\) tuyến tàu điện, mỗi tuyến nối hai cửa hàng với một chính sách giá vé đặc biệt. Tuyến thứ \(i\) di chuyển hai chiều giữa cửa hàng \(u_i\) và \(v_i\), với hai mức giá vé là \(w_i\) và \(l_i\) đồng (\(l_i \le w_i\)). Cụ thể, nếu bạn mua vé tuyến này lần đầu tiên trong ngày, bạn phải trả \(w_i\) đồng. Tuy nhiên, nếu bạn đi lại trên cùng tuyến đó trong ngày, mỗi vé tiếp theo sẽ chỉ tốn \(l_i\) đồng. Mạng lưới này đảm bảo đều hai cửa hàng bất kì đều có thể di chuyển đến nhau.

Minh xuất phát từ cửa hàng \(1\) và anh ta cần phải đến một cửa hàng bất kỳ để mua bộ vi xử lý, sau đó anh ta sẽ đi đến một cửa hàng khác để mua card đồ họa. Sau khi mua đủ linh kiện, anh ta sẽ quay trở lại cửa hàng \(n\) để bắt đầu lắp ráp.

Yêu cầu: Hãy giúp Minh tìm lộ trình sao cho tổng số tiền chi tiêu (bao gồm cả tiền mua linh kiện và tiền di chuyển) là ít nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m\) \((1 \leq n, m \leq 10^5)\).
• Dòng tiếp theo chứa \(n\) số tự nhiên: \(c_1, c_2, \ldots, c_n\) \((0 \leq c_i \leq 10^9)\), là giá của bộ vi xử lý ở mỗi cửa hàng.
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số: \(u_i, v_i, w_i, l_i\), là thông tin về tuyến tàu điện. \((1 \leq u_i, v_i \leq n, 0 \leq l_i \leq w_i \leq 10^9)\).
• Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là tổng số tiền nhỏ nhất có thể.

Example

5 6
10 10 1 10 10
1 2 2 2
2 3 1 1
3 4 1 1
4 5 2 2
1 5 1 1
2 5 2 0

6

Scoring

• Có \(25\%\) số test tương ứng với \(25\%\) số điểm : \(n, m \leq 100\)
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm : \(n, m \leq 1000\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm : \(w_i = l_i\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm còn lại không có ràng buộc gì thêm.