Theo quy định, giá điện được chia làm 3 loại: Điện sinh hoạt, điện sản xuất và điện kinh doanh. Giá điện sinh hoạt hàng tháng đối với mỗi hộ gia đình tiêu thụ điện được tính theo 4 bậc:

• Bậc 1: Với ~50~ kWh đầu tiên, mỗi kWh được tính với giá ~x_1~ đồng;
• Bậc 2: Từ kWh thứ ~51~ đến kWh thứ ~100~ được tính với giá ~x_2~ đồng;
• Bậc 3: Từ kWh thứ ~101~ đến kWh thứ ~200~ được tính với giá ~x_3~ đồng;
• Bậc 4: Từ kWh thứ ~201~ trở lên được tính với giá ~x_4~ đồng.

Yêu cầu

Cho biết lượng điện tiêu thụ của một gia đình trong một tháng là ~y~ kWh, hãy tính số tiền điện trong tháng gia đình đó phải trả theo giá điện sinh hoạt.

Input

Dòng đầu tiên chứa 4 số nguyên ~x_1, x_2, x_3, x_4~ (~0 < x_1 < x_2 < x_3 < x_4 < 10^4~) tương ứng giá điện sinh hoạt 4 bậc nêu trên.

Dòng thứ 2 chứa một số nguyên ~y~ (~0 ≤ y ≤ 10^9~) là lượng điện tiêu thụ trong tháng.

Output

Một số nguyên duy nhất là số tiền điện phải trả trong tháng

Sample Test

Input

1800 1900 2100 2700
300

Output

665000

Ràng buộc:

• Có ~70\%~ số test ứng với ~70\%~ số điểm thỏa mãn: ~0 ≤ y ≤ 10^5~;
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm không có ràng buộc gì thêm.

Cho số nguyên dương ~n~ và dãy số nguyên ~a_1, a_2, \dots, a_n~. Hãy tìm dãy số ~B~ sao cho ~b_i = a_1 + a_2 + \dots + a_i~, hay nói cách khác ~b_i~ là tổng của ~i~ số đầu tiên trong dãy ~A~.

Input

• Dòng đầu tiên ghi số nguyên dương ~n~ (~1 \leq n \leq 10^6~).
• Dòng tiếp theo ghi lần lượt các số ~a_1, a_2, \dots, a_n~ (~|a_i| \leq 10^9~).

Output

Ghi lần lượt các số ~b_1, b_2, \dots, b_n~.

Sample Test

Input

4
1 4 3 2

Output

1 5 8 10