Bạn là quản lý của ca sĩ nổi tiếng Bích Phương. Tháng này, Bích Phương sẽ có một tour diễn kéo dài trong D ngày. Để tổ chức tour, đất nước được chia thành C khu vực khác nhau. Mỗi lần Bích Phương biểu diễn tại một khu vực, cô ấy sẽ nhận được một khoản lợi nhuận (số nguyên dương).

Theo quy tắc, Bích Phương chỉ có thể biểu diễn tối đa 1 buổi mỗi ngày. Tuy nhiên, nếu Bích Phương biểu diễn tại một khu vực và sau đó có thể di chuyển ngay đến khu vực liền kề, cô ấy có thể biểu diễn thêm một buổi nữa ngay trong ngày đó. Điều kiện là Bích Phương không được biểu diễn tại cùng một khu vực nhiều hơn một lần trong cùng một ngày.

Số ngày mà Bích Phương có thể biểu diễn nhiều hơn 1 buổi trong cùng một ngày không được vượt quá tổng số ngày X trong suốt tour diễn.

Là người phụ trách lịch trình cho Bích Phương, nhiệm vụ của bạn là tìm ra phương án tổ chức các buổi biểu diễn sao cho tổng lợi nhuận là lớn nhất. Mỗi buổi biểu diễn sẽ khiến Bích Phương chịu một mức độ mệt mỏi (là một số nguyên không âm) và tổng mức độ mệt mỏi trong tour diễn phải nhỏ hơn hoặc bằng W.

Bạn cần đọc vào mức độ mệt mỏi và lợi nhuận mong đợi từ mỗi buổi biểu diễn, rồi xây dựng lịch trình tạm thời sao cho tổng lợi nhuận đạt giá trị lớn nhất.

Dữ liệu bao gồm nhiều bộ kiểm tra. Mỗi bộ kiểm tra có dạng:

• Dòng đầu tiên gồm bốn số nguyên:

  • C: số lượng khu vực
  • D: số ngày trong tour diễn
  • W: tổng mức độ mệt mỏi tối đa Bích Phương có thể chịu được
  • X: số ngày tối đa Bích Phương có thể biểu diễn nhiều hơn một buổi trong cùng một ngày.

• Tiếp theo là một bảng C \times D: Các giá trị Ei,j (với 1 \leq i \leq C và 1 \leq j \leq D) biểu diễn lợi nhuận mong đợi nếu Bích Phương biểu diễn tại khu vực i vào ngày j. Nếu Ei,j = 0, điều đó có nghĩa là không thể tổ chức buổi biểu diễn tại khu vực này trong ngày đó.

• Sau bảng lợi nhuận là bảng C \times D thứ hai: Các giá trị Fi,j biểu diễn mức độ mệt mỏi mà Bích Phương sẽ chịu nếu biểu diễn tại khu vực i vào ngày j. Nếu Ei,j = 0, giá trị Fi,j cũng sẽ bằng 0.

Các khu vực được xác định như sau:

• Khu vực i và khu vực i+1 hoặc i-1 được xem là liền kề.
• Lưu ý rằng khu vực 1 và khu vực C không liền kề nhau (với C > 2).

Dữ liệu đầu vào kết thúc khi xuất hiện dòng chứa 0 0 0 0.

Với mỗi bộ kiểm tra, in ra một dòng duy nhất là tổng lợi nhuận tối đa có thể đạt được.

Các giá trị đều là số nguyên.

• 1 \leq C \leq 15.
• 1 \leq D \leq 30.
• 0 \leq W \leq 50.
• 0 \leq X \leq 5.
• 0 \leq E_{i,j} \leq 1000.
• 0 \leq F_{i,j} \leq 10.
• Số bộ kiểm tra không vượt quá 100.