INCMAT - Học toán
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Nam được mẹ giao nhiệm vụ rèn luyện phép tính cộng cho em trai. Nam dự định vừa rèn luyện tính cộng vừa tạo niềm yêu thích tin học bằng cách cho em trai giải bài toán sau:

Cho một bảng số nguyên gồm có 𝑚 hàng và 𝑛 cột. Các hàng của bảng được đánh số từ 1 tới 𝑚 từ trên xuống dưới, các cột của bảng số được đánh số từ 1 tới 𝑛 từ trái qua phải. Giá trị của số nằm ở hàng 𝑖, cột 𝑗 (1 ≤ 𝑖 ≤ 𝑚; 1 ≤ 𝑗 ≤ 𝑛) được ký hiệu là 𝑎(𝑖,𝑗). Cần thực hiện lần lượt 𝑄 thao tác, thao tác thứ 𝑡 (1 ≤ 𝑡 ≤ 𝑄) được mô tả bằng bộ năm số 𝑥𝑡 , 𝑦𝑡 , 𝑢𝑡 , 𝑣𝑡 , 𝑐𝑡 , thao tác này sẽ tăng tất cả các phần tử 𝑎(𝑖,𝑗) với mọi 𝑥𝑡 ≤ 𝑖 ≤ 𝑢𝑡 , 𝑦𝑡 ≤ 𝑗 ≤ 𝑣𝑡 lên một lượng là 𝑐𝑡 (𝑐𝑡 > 0).

Nam sẽ yêu cầu em trai ghi ra giấy tất cả các phần tử của bảng số sau khi đã thực hiện cả 𝑄 thao tác. Để kiểm tra xem em mình làm có đúng không, Nam phải tự mình tính toán ra được kết quả đúng trước đã. Sau một hồi tính toán, Nam đã có được bảng số sau khi thực hiện 𝑄 thao tác. Tuy nhiên, giá trị của các phần tử của bảng số kết quả khá lớn! Nam sợ rằng em trai mình sẽ gặp khó khăn khi thực hiện phép cộng giữa hai số lớn, do đó Nam quyết định bỏ đi một thao tác sao cho sau khi thực hiện 𝑄 − 1 thao tác còn lại, giá trị lớn nhất của bảng số là nhỏ nhất có thể.

Yêu cầu: Cho bảng số và dãy 𝑄 thao tác, gọi 𝑊𝑡 là giá trị lớn nhất trong bảng sau bỏ đi thao tác thứ 𝑡 (1 ≤ 𝑡 ≤ 𝑄), tính Min{𝑊1,𝑊2, … , 𝑊𝑄}.

Dữ liệu:

- Dòng đầu chứa số hai số nguyên dương 𝑚, 𝑛;
- Tiếp theo là 𝑚 dòng, dòng thứ 𝑖 (1 ≤ 𝑖 ≤ 𝑚) gồm 𝑛 số nguyên không âm 𝑎(𝑖, 1), 𝑎(𝑖, 2), …, 𝑎(𝑖, 𝑛), các số có giá trị không vượt quá 109.
- Dòng tiếp theo chứa số nguyên 𝑄 (𝑄 > 1);
- Tiếp theo là 𝑞 dòng, dòng thứ 𝑡 (1 ≤ 𝑡 ≤ 𝑄) gồm 5 số nguyên 𝑥𝑡 , 𝑦𝑡 , 𝑢𝑡 , 𝑣𝑡 , 𝑐𝑡 (1 ≤ 𝑥𝑡 ≤ 𝑢𝑡 ≤ 𝑚, 1 ≤ 𝑦𝑡 ≤ 𝑣𝑡 ≤ 𝑛, 1 ≤ 𝑐𝑡 ≤ 1000).

Kết quả:

Ghi ra một dòng duy nhất là giá trị nhỏ nhất của giá trị lớn nhất của bảng số sau khi loại bỏ đi đúng một thao tác.

Ví dụ

Input

4 4
1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1
3
1 1 3 3 2
2 2 3 4 1
3 1 4 3 2

Output

3

Giới hạn 

- Có 20% số test có 𝑚 = 1; 𝑛, 𝑞 ≤ 500;
- Có 20% số test khác có 𝑞, 𝑚, 𝑛 ≤ 500;
- Có 25% số test khác có 𝑚 = 1; 𝑛 ≤ 106 ; 𝑄 ≤ 106 ;
- Có 25% số test khác có 𝑚, 𝑛 ≤ 1000; 𝑄 ≤ 106 ;
- Có 10% số test còn lại có 𝑚 × 𝑛 ≤ 106 ; 𝑄 ≤ 106 .


Nguồn: 3D '1819

Back to Top