Một khách sạn phục vụ khách đến nghỉ rất chu đáo và tiện nghi: hằng ngày khách sạn đều thay chăn màn cho các phòng. Giả sử các bộ chăn màn ở các phòng là như nhau về kích thước và giá cả. Khách đến nghỉ ở khách sạn phải đặt phòng trước để người phục vụ dọn dẹp chuẩn bị phòng trước khi khách nhận phòng. Giả sử có ~N~ ngày liên tiếp được đánh số từ ~1~ đến ~N~, tương ứng có ~D_1, D_2,..., D_N~ phòng được đặt (nghĩa là khách sạn phải chuẩn bị ~D_1, D_2,... , D_N~ chăn màn cho các phòng được đặt tương ứng trong ~N~ ngày đó). Để có lợi nhuận cao nhất và phục vụ tốt cho khách đến khách sạn nghỉ, người quản lý khách sạn có ~3~ phương án lựa chọn: mua chăn màn mới với chi phí ~A~ (đương nhiên khách sạn phải mua cho ngày phục vụ đầu tiên) hoặc giặt lấy nhanh bằng cách gửi giặt ở các hiệu giặt và lấy chăn màn sạch để sử dụng vào ngày hôm sau thì phải trả ~B~ đồng cho một bộ chăn màn hoặc giặt lấy chậm bằng cách gửi giặt vào ngày thứ ~i~ và lấy chăn màn sạch để sử dụng vào ngày thứ ~i+2~ thì phải trả ~C~ đồng một bộ chăn màn.

Yêu cầu:

Hãy giúp người quản lý mua và giặt chăn màn sao cho có lợi nhất (ít tốn chi phí nhất). Người quản lý khách sạn sẽ cám ơn bạn rất nhiều và có thể sẽ có ưu đãi đối với bạn khi bạn đến khách sạn của họ để nghỉ.

Dữ liệu vào:

• Dòng đầu tiên gồm ~4~ số nguyên dương ~N, A, B, C (N<100, 20 > A>B>C>0)~.
• Dòng thứ hai gồm ~N~ số nguyên không âm ~D_1, D_2,..., D_N~ ~(D_i \le 50)~.

Kết quả:

Gồm ~N + 1~ dòng:

• Dòng đầu tiên: tổng chi phí nhỏ nhất.
• Dòng ~i + 1~ ~(1 \leq i \leq N)~: ghi ~3~ số nguyên không âm ~M_i, F_i, S_i~ theo thứ tự là số chăn màn mới cần mua, số chăn màn giặt lấy nhanh, số chăn màn giặt lấy chậm trong ngày thứ ~i~.

Sample Input

10 10 3 2
10  8  9  20  7  1  7  9  8  3

Sample Output

340
20  0  10
0  0  8
0  9  0
0  7 13
0  0  7
0  0  1
0  0  7
0  0  0
0  0  0
0  0  0