Nữ hoàng Elizabeth của vương quốc Alpha rất thích sưu tầm các loại trang sức, trong đó nổi bật nhất là bộ sưu tập gồm ~N~ viên đá quý, được đánh số từ ~1~ đến ~N~. Vào bữa tiệc sinh nhật của mình, Nữ hoàng dự định sẽ mang một bộ trang sức thật lộng lẫy gồm có một chiếc vòng cổ và ~X~ chiếc nhẫn. Các chiếc nhẫn được đánh số từ ~1~ đến ~X~. Vì vậy Nữ hoàng đã thuê một thợ kim hoàn chọn ~X~ viên đá quý trong số này để đính vào các chiếc nhẫn (mỗi chiếc nhẫn được đính một viên đá quý) và chọn ~Y~ viên đá quý để đính vào chiếc vòng cổ. Biết rằng viên đá quý ~i~ nếu được đính vào chiếc nhẫn ~j~ sẽ có độ lộng lẫy ~a_{ij}~, còn nếu được đính vào chiếc vòng cổ sẽ có độ lộng lẫy ~b_i~.

Người thợ kim hoàn rất phân vân chưa biết chọn và đính những viên đá quý như thế nào để bộ trang sức Nữ hoàng mang là lộng lẫy nhất vào ngày hôm ấy.

Yêu cầu: Hãy tính độ lộng lẫy tối đa của bộ trang sức được Nữ hoàng mang vào bữa tiệc sinh nhật.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~N, X, Y~ ~(2 \le N \le 10^5; X \le 7; Y, X+Y \le N)~;

• Dòng thứ hai chứa ~N~ số nguyên dương ~b_1, b_2, \dots, b_N~ lần lượt là độ lộng lẫy của viên đá quý thứ ~i~ nếu được gắn vào chiếc vòng cổ ~(b_i \le 10^9)~;

• Dòng thứ ~i~ trong ~N~ dòng tiếp theo chứa ~X~ số nguyên dương ~a_{ij}~ mô tả độ lộng lẫy của viên đá quý ~i~ nếu được gắn vào chiếc nhẫn ~j~ ~(1 \le i \le N; 1 \le j \le X; a_{ij} \le 10^9)~.

Output

Một số nguyên duy nhất là độ lộng lẫy tối đa của bộ trang sức.

Scoring

Sample Input 1

4 1 2
6 3 5 2
3
2
4
3

Sample Output 1

14

Notes

Viên đá thứ tư được đính vào nhẫn, hai viên đá thứ nhất và thứ ba được đính vào vòng cổ. Tổng độ lộng lẫy là: ~3 + 6 + 5 = 14~.