Tin học trẻ B - Vòng Khu vực miền Bắc và miền Trung 2020

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

3 4 2 2
1 -1 2
1 1 1 1

6

Hội thi Tin học trẻ được tổ chức hàng năm và đã thu hút được sự quan tâm của cả nước. Đề thi ngày càng phong phú và đa dạng là do sự đóng góp ý tưởng từ rất nhiều nhà khoa học và các tổ chức công nghệ. Đến nay, ngân hàng đề thi có tổng cộng \(n\) bài, các bài được đánh số từ \(1\) tới \(n\), bài thứ \(i\) có độ khó là \(i\). Để xây dựng đề thi năm nay, Ban giáo khảo muốn chọn \(k\) bài khác nhau từ ngân hàng đề thi mà tổng độ khó của \(k\) bài đúng bằng \(n\). Để khảo sát tính đa dạng của đề thi, Ban giám khảo muốn tính số cách xây dựng đề thi khác nhau (hai đề thi được gọi là khác nhau nếu có một bài được chọn trong đề thứ nhất nhưng không được chọn trong đề thứ hai).

Hãy giúp Ban giám khảo tính số cách xây dựng đề thi khác nhau. Vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư của phép chia kết quả tìm được cho \((10^9 + 7)\).

Input

• Một dòng duy nhất chứa hai số nguyên dương \(n\) và \(k\).

Output

• Ghi ra một số nguyên duy nhất là số dư của phép chia kết quả tìm được cho \((10^9 + 7)\).

Example

10 3

4

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\) và \(k \le 5\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 10^6\) và \(k \le 5\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^9\) và \(k = 2\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^9\) và \(k = 3\).
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^9\) và \(k \le 5\).