Cướp biển Râu Đen có ~n~ viên đá quý. Hắn muốn chọn ~x~ viên đá để đính lên ~x~ chiếc nhẫn, mỗi chiếc nhẫn nhận đúng một viên đá, và chọn thêm ~y~ viên đá khác để đính vào vòng cổ. Mỗi viên đá chỉ được sử dụng một lần.

Nếu viên đá thứ ~i~ được đính vào chiếc nhẫn thứ ~j~ thì có độ lộng lẫy ~s_{i,j}~. Nếu viên đá thứ ~i~ được đính vào vòng cổ thì có độ lộng lẫy ~a_i~.

Yêu cầu: Hãy tính tổng độ lộng lẫy lớn nhất của bộ trang sức có thể tạo được.

Input

• 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,\dots,a_n~ ~(1 \le a_i \le 10^9)~;

• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~x~ số nguyên ~s_{i,1},s_{i,2},\dots,s_{i,x}~ ~(1 \le s_{i,j} \le 10^9)~.

Output

In ra một số nguyên duy nhất là tổng độ lộng lẫy lớn nhất của bộ trang sức.

Scoring

Sample Input 1

4 1 2
1 16 10 3
18
19
13
15

Sample Output 1

44

Sample Input 2

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

Sample Output 2

422899

Sample Input 3

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

Sample Output 3

377