Phần thưởng (Tin học trẻ BC - Vòng Khu vực miền Bắc miền Trung 2020)

Xem PDF

Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

An là người thắng cuộc trong cuộc thi "Tìm hiểu Đoàn Thanh niên Cộng sản Hồ Chí Minh" và được nhận phần thưởng của Ban tổ chức. Ban tổ chức chuẩn bị một bảng kích thước \(m \times n\). Các dòng của bảng được đánh số từ \(1\) đến \(m\), từ trên xuống dưới, dòng \(i\) (\(1 \le i \le m\)) có trọng số là \(a_i\). Các cột của bảng được đánh số từ \(1\) đến \(n\), từ trái qua phải, cột \(j\) (\(1 \le j \le n\)) có trọng số là \(b_j\). Ô nằm trên giao của dòng \(i\) và cột \(j\) được gọi là ô (\(i,j\)) và trên ô đó ghi một số nguyên có giá trị \(a_i + b_j\) (\(1 \le i \le m, 1 \le j \le n\)).

Để nhận phần thưởng, An được phép chọn một bảng có kích thước \(w \times h\) chiếm trọn \(w \times h\) ô của bảng và phần thưởng mà An nhận được sẽ có giá trị bằng tổng giá trị các ô nằm trong bảng con đó.

Yêu cầu: Hãy xác định tổng giá trị lớn nhất mà An có thể nhận được.

Input

  • Dòng thứ nhất chứa bốn số nguyên dương \(m,n,w,h\) (\(w \le m, h \le n\)).
  • Dòng thứ hai chứa \(m\) số nguyên \(a_1,a_2,...,a_m\) (\(|a_i| \le 10^6, i = 1,2,...,m\)).
  • Dòng thứ ba chứa \(n\) số nguyên \(b_1,b_2,...,b_n\) (\(|b_j| \le 10^6, j = 1,2,...,n\)).

Output

  • Một số nguyên duy nhất là tổng giá tri lớn nhất mà An có thể nhận được.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(m,n \le 10, w = h = 1\).
  • Subtask \(2\) (\(30\%\) số điểm): \(m,n \le 10\).
  • Subtask \(3\) (\(20\%\) số điểm): \(m,n \le 10^3\).
  • Subtask \(4\) (\(30\%\) số điểm): \(m,n \le 10^5\).

Example

Test 1
Input
3 4 2 2
1 -1 2
1 1 1 1
Output
6
Note


Bảng kích thước \(3 \times 4\), trọng số của các hàng và các cột được ghi trong ngoặc ở hàng và cột tương ứng. Một cách chọn bảng con kích thước \(2 \times 2\) là hình được tô màu có tổng giá trị bằng \(6\).


Bình luận

Không có bình luận nào.