Ăn khế trả vàng

Sau nhiều lần được ăn khế, quạ hứa sẽ trả vàng. Bác nông dân đã may đúng túi ba gang. Và mỗi lần trải qua nhiều ngày được quạ tha đi lĩnh đênh trên biển, Bác đã thu về cho mình một khối gia tài đồ sộ. Trong đó nổi bật nhất là kho báu không chỉ vàng mà còn có thêm đá quý. Có \(n\) viên đá quý, ông quyết định sẽ dùng \(x\) viên đá quý trong số này để đính vào nhẫn, và chọn ra \(y\) viên đá quý để đính vào vòng cổ để có thể phô trương độ giàu có của mình.

Mỗi một viên đá quý, viên thứ \(i\) nếu được đính vào chiếc nhẫn thứ \(j\) sẽ có độ lộng lẫy \(s_{ij}\), còn nếu được đính vào vòng cổ sẽ có độ lộng lẫy \(a_i\). Mỗi chiếc nhẫn được đính đúng một viên đá quý, mỗi viên đá quý được dùng tối đa một lần. Nam được thuê làm thợ kim hoàn cho lão nông. Dù đang bận ôn thi học sinh giỏi cấp tỉnh, nhưng cậu cũng muốn kiếm ít kinh phí để lo cho việc học, với mức kinh phí được trả rất hậu hĩnh vì thế Nam ngay lập tức nhận lời.

Yêu cầu: Hãy tính độ lộng lẫy tối đa của bộ trang sức cho lão nông mà Nam có thể tạo được (tổng độ lộng lẫy của \(x\) viên đá trên các nhẫn và \(y\) viên đá trên vòng cổ).

Input

Dữ liệu vào gồm

• Dòng đầu tiên chứa ba số nguyên \(n, x, y\) (\(2 \le n \le 10^5\), \(1 \le x \le 7\), \(1 \le y\), \(x + y \le n\));

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) lần lượt là độ lộng lẫy của viên đá thứ \(i\) nếu được gắn vào vòng cổ (\(1 \le a_i \le 10^9\));

• \(n\) dòng tiếp theo, mỗi dòng chứa \(x\) số nguyên \(s_{i1}, s_{i2}, \ldots, s_{ix}\), mô tả độ lộng lẫy của viên đá thứ \(i\) nếu được gắn vào chiếc nhẫn thứ \(j\) (\(1 \le s_{ij} \le 10^9\)).

Ràng buộc:

• Subtask 1: Có \(20\%\) điểm tương ứng \(20\%\) test với \(n \le 7\);

• Subtask 2: Có \(20\%\) điểm tương ứng \(20\%\) test với \(x = 1\);

• Subtask 3: Có \(20\%\) điểm tương ứng \(20\%\) test với \(a_1 = a_2 = \cdots = a_n\);

• Subtask 4: Có \(40\%\) điểm tương ứng \(40\%\) test không có ràng buộc gì thêm.

Output

In ra một số duy nhất là độ đẹp tối đa của bộ trang sức cho bác nông dân mà Nam có thể tạo ra.

Example 1

Input:

4 1 2
1 16 10 3
18
19
13
15

Output:

44

Example 2

Input:

3 2 1
500 498 564
100002 3
422332 2
232323 1

Output:

422899

Example 3

Input:

6 2 3
78 93 9 17 13 78
80 97
30 52
26 17
56 68
60 36
84 55

Output:

377

Note

Ví dụ 1: đính viên thứ nhất vào nhẫn (\(18\)), viên thứ hai và thứ ba vào vòng cổ (\(16 + 10\)), tổng \(44\).

Ví dụ 2: viên thứ hai vào nhẫn \(1\) (\(422332\)), viên thứ nhất vào nhẫn \(2\) (\(3\)), viên thứ ba vào vòng cổ (\(564\)), tổng \(422899\).

Ví dụ 3: có hai nhẫn và ba viên cho vòng cổ. Chọn các viên \(1, 2, 6\) cho vòng cổ (\(78 + 93 + 78 = 249\)), viên \(5\) vào nhẫn \(1\) (\(60\)) và viên \(4\) vào nhẫn \(2\) (\(68\)), tổng \(377\).