Một tiệm bánh bán bánh với những cây nến hình số. Có \(X\), \(Y\) và \(Z\) loại bánh với nến hình số \(1\), \(2\) và \(3\) tương ứng. Mỗi chiếc bánh có một giá trị nguyên được gọi là độ ngon, như sau:

• Độ ngon của các chiếc bánh với nến hình số \(1\) là \(A_1, A_2, ..., A_X\).
• Độ ngon của các chiếc bánh với nến hình số \(2\) là \(B_1, B_2, ..., B_Y\).
• Độ ngon của các chiếc bánh với nến hình số \(3\) là \(C_1, C_2, ..., C_Z\).

Quang quyết định mua ba chiếc bánh, mỗi chiếc có một hình dạng nến khác nhau.

Có \(X \times Y \times Z\) cách để chọn ba chiếc bánh.

Chúng ta sẽ sắp xếp \(X \times Y \times Z\) cách này theo thứ tự giảm dần của tổng độ ngon của các chiếc bánh.

In ra các tổng độ ngon của các chiếc bánh cho cách thứ nhất, thứ hai, ..., thứ \(K\) trong danh sách này.

Ràng buộc

• \(1 \leq X \leq 1 000\)
• \(1 \leq Y \leq 1 000\)
• \(1 \leq Z \leq 1 000\)
• \(1 \leq K \leq min(3 000, X \times Y \times Z)\)
• \(1 \leq A_i \leq 10 000 000 000\)
• \(1 \leq B_i \leq 10 000 000 000\)
• \(1 \leq C_i \leq 10 000 000 000\)

Tất cả các giá trị đầu vào là số nguyên.

INPUT FORMAT

• Đầu vào được cung cấp từ Standard Input theo định dạng sau:

  X
  Y
  Z
  K
  A_1 A_2 ... A_X
  B_1 B_2 ... B_Y
  C_1 C_2 ... C_Z

OUTPUT FORMAT

• In ra \(K\) dòng. Dòng thứ \(i\) chứa giá trị thứ \(i\) được nêu trong đề bài.

Ví dụ:

Input

2 2 2 8
4 6
1 5
3 8

Output

19
17
15
14
13
12
10
8

Có \(2 imes 2 imes 2 = 8\) cách để chọn ba chiếc bánh, như sau theo thứ tự giảm dần của tổng độ ngon của các chiếc bánh:

• \((A_2, B_2, C_2): 6 + 5 + 8 = 19\)
• \((A_1, B_2, C_2): 4 + 5 + 8 = 17\)
• \((A_2, B_1, C_2): 6 + 1 + 8 = 15\)
• \((A_2, B_2, C_1): 6 + 5 + 3 = 14\)
• \((A_1, B_1, C_2): 4 + 1 + 8 = 13\)
• \((A_1, B_2, C_1): 4 + 5 + 3 = 12\)
• \((A_2, B_1, C_1): 6 + 1 + 3 = 10\)
• \((A_1, B_1, C_1): 4 + 1 + 3 = 8\)

Input

3 3 3 5
1 10 100
2 20 200
1 10 100

Output

400
310
310
301
301

Có thể có nhiều cách kết hợp bánh với cùng một tổng độ ngon. Ví dụ, trong bài kiểm tra này, tổng độ ngon của \(A_1, B_3, C_3\) và tổng độ ngon của \(A_3, B_3, C_1\) đều là \(301\). Tuy nhiên, chúng là những cách chọn bánh khác nhau, nên \(301\) xuất hiện hai lần trong kết quả đầu ra.

Giải thích ví dụ mẫu

Ví dụ 1:

• Input:

  2 2 2 8 4 6 1 5 3 8

• Giải thích:

  • Có 8 cách chọn bánh, và tổng độ ngon cao nhất là 19 từ sự kết hợp của chiếc bánh ngon nhất từ mỗi loại.

Ví dụ 2:

• Input:

  3 3 3 5 1 10 100 2 20 200 1 10 100

• Giải thích:

  • Kết hợp các chiếc bánh tạo ra nhiều tổng độ ngon giống nhau, ví dụ như 301 xuất hiện hai lần từ các lựa chọn khác nhau.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House