SuperCoders là đội gồm 3 thành viên: Khương, Thanh và Thành dự cuộc thi Hackathon của trường mầm non SuperKids. Theo thể thức của cuộc thi, mỗi đội chỉ được giao duy nhất một máy tính để làm k bài thi đánh số từ 1 tới k. Thời gian làm bài không hạn chế, nhưng phải làm xong hết k bài mới được xếp hạng. Đội nào xong càng sớm sẽ có thứ hạng càng cao. Với luật thi như vậy, việc phân phối công việc kết hợp với nghỉ ngơi là điều hết sức quan trọng. Sau khi hội ý, các thành viên quyết định rằng mỗi bài sẽ chỉ giao cho một trong ba người làm và các bài sẽ được giải quyết một cách tuần tự trên máy tính duy nhất của đội:

• Khương sẽ làm đúng m bài, nếu Khương làm bài thứ i sẽ mất ~a_i~ giây
• Thanh sẽ làm đúng n bài, nếu Thanh làm bài thứ i sẽ mất ~b_i~ giây
• Thành sẽ làm đúng p bài, nếu Thành làm bài thứ i sẽ mất ~c_i~ giây

Ở đây~ m+n+p=k~

Yêu cầu: Hãy giúp đội SuperCoders tìm ra cách phân công để mỗi người làm đúng số bài đã định sao cho tổng thời gian làm cả k bài là ít nhất.

Dữ liệu:

• Dòng 1 chứa ba số nguyên dương ~m,n,p≤10^5~
• ~m+n+p~ dòng tiếp theo, dòng thứ i chứa ba số nguyên dương ~a_i,b_i,c_i≤10^6~

Các số trên cùng một dòng của input được ghi cách nhau bởi dấu cách

Kết quả: Ghi ra một số nguyên duy nhất là tổng thời gian làm tất cả các bài theo phương án phân công tối ưu tìm được.

Ví dụ

INPUT

2 3 4
1 3 8
1 4 5
1 5 6
9 3 4
9 4 5
9 5 6
6 6 6
6 6 6
6 6 6

OUTPUT

36

Bộ test chia làm 3 subtasks:

• Subtask 1 (25% số điểm): k≤20
• Subtask 2 (25% số điểm): k≤2000
• Subtask 3 (50% số điểm): Không có ràng buộc bổ sung