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ứ hai chứa một số nguyên ~y~ ~\ (0 \leq y \leq 10^9)~ là lượng điện tiêu thụ trong tháng.
• Các số trên một dòng cách nhau ít nhất 1 dấu cách.

Output

• In ra một số nguyên là số tiền điện phải trả trong tháng.

Sample Input

1800 1900 2100 2700 300
300

Sample Output

665000

Subtasks

• Có 70% số test ứng với 70% số điểm thỏa mãn: ~0 \leq y \leq 10^5~.
• 30% số test còn lại 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 dương gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~.

Yêu cầu: Hãy đưa ra số lượng ước nguyên dương của một phần tử có nhiều ước nguyên dương nhất trong dãy số đã cho.

Input

• Dòng 1 chứa số nguyên dương ~n~ ~\ (1 \leq n \leq 10^6)~.
• Dòng 2 chứa ~n~ số nguyên là giá trị của các phần tử ~a_1, a_2, \dots, a_n~ ~\ (1 \leq a_i \leq 10^6)~.

Output

• In ra một số nguyên là kết quả bài toán.

Sample Input

4 
3 8 16 22

Sample Output

5

Phần tử ~a_3 = 16~ là phần tử có nhiều ước dương nhất trong dãy số, gồm 5 ước dương là ~1, 2, 4, 8, 16~ nên kết quả là ~5~.

Sample Input

5 
3 5 6 7 8

Sample Output

4

Phần tử ~a_3 = 6~ là phần tử có nhiều ước dương nhất trong dãy số, gồm 4 ước dương là ~1, 2, 3, 6~ nên kết quả là ~4~.

Subtasks

• Có 70% số test ứng với 70% số điểm thỏa mãn: ~n \leq 10^3~ và ~a_i \leq 10^3~.
• Có 15% số test ứng với 15% số điểm thỏa mãn: ~n \leq 10^3~ và ~a_i \leq 10^6~.
• 15% số test còn lại ứng với 15% 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 không âm gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~. Hãy cho biết có bao nhiêu cách chọn cặp chỉ số ~(i, j)~, trong đó ~(1 \leq i, j \leq n; i \neq j)~ sao cho sau khi xóa 2 phần tử ~a_i, a_j~ khỏi dãy thì tổng giá trị các phần tử còn lại trong dãy là số chẵn.

Hai cặp chỉ số được chọn ~(i, j)~ và ~(j, i)~ được tính là 1 cách chọn; hai cách chọn được coi là khác nhau nếu tồn tại ít nhất một chỉ số khác nhau.

Input

• Dòng 1 chứa số nguyên dương ~n~ ~(2 \leq n \leq 10^6)~.
• Dòng 2 chứa ~n~ số nguyên là giá trị của các phần tử ~a_1, a_2, \dots, a_n~ ~(0 \leq a_i \leq 10^6)~.

Output

• In ra một số nguyên là kết quả bài toán.

Sample Input

5 
1 6 3 8 4

Sample Output

4

Có ~4~ cách chọn cặp chỉ số ~(i, j)~:

• Cách 1: chọn cặp ~(i = 1, j = 3)~ tổng còn lại; ~a_2 + a_4 + a_5 = 6 + 8 + 4 = 18~ là số chẵn.
• Tương tự có thêm các cách chọn cặp ~(i, j)~ là: ~(2, 4); (2, 5); (4, 5)~

Subtasks

• Có 50% số test ứng với 50% số điểm thỏa mãn: ~n \leq 10^3~.
• 50% số test còn lại ứng với 50% số điểm không có ràng buộc gì thêm.

Để thực hiện dự án phủ sóng viễn thông trên một tuyến phố mới mở, nhà cung cấp dịch vụ VT đã tiến hành đánh giá từ vị trí đầu tuyến phố, bắt đầu là vị trí 0 tới tiếp theo là các điểm ~1, 2, 3, \ldots~ Sau đó khảo sát số lượng người có nhu cầu sử dụng dịch vụ và đã xác định được các điểm dân cư tại 1 số vị trí đã được đánh dấu; điểm dân cư tại vị trí ~x~ (~x \ge 1~) có số lượng người có nhu cầu sử dụng dịch vụ là ~y~.

Chú ý mỗi trạm phát sóng có bán kính phủ sóng là ~k~ đơn vị chiều dài (một đơn vị chiều dài là khoảng cách giữa hai vị trí kề nhau), hãy giúp nhà cung cấp dịch vụ chọn 1 vị trí đã được đánh dấu trên tuyến phố để đặt trạm phát sóng sao cho phục vụ được nhiều nhất số người có nhu cầu sử dụng dịch vụ.

Yêu cầu: Đưa ra số lượng lớn nhất người có nhu cầu sử dụng dịch vụ sẽ được phủ sóng khi chọn được vị trí đặt trạm phát sóng.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \leq n \leq 10^6~, ~1 \leq k \leq 10^9~), trong đó ~n~ là số điểm cần đã được xác định, ~k~ là bán kính phủ sóng của trạm.
• Trong ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x~ và ~y~ (~1 \leq x \leq 10^9~), cho biết dân cư tại vị trí ~x~ có số lượng người sử dụng dịch vụ là ~y~.
• Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

• In ra một số nguyên là số người có nhu cầu sử dụng dịch vụ lớn nhất sẽ được phủ sóng.

Sample Input

4 3
2 8
7 2
10 6
1 4

Sample Output

14

Số người có nhu cầu sử dụng dịch vụ lớn nhất sẽ được phủ sống là ~14~, khi đặt trạm phát sóng tại vị trí ~x = 4~ (có thể phủ sống đến các vị trí có tọa độ ~1, 2, 7~ tương ứng có ~4 + 8 + 2 = 14~ người có nhu cầu sử dụng dịch vụ).

Subtasks

• Có 40% số test ứng với 40% số điểm thỏa mãn: ~n \leq 10^3~ và ~x \leq 10^3~
• Có 40% số test ứng với 40% số điểm thỏa mãn: ~n \leq 10^5~ và ~10^6 \leq x \leq 10^9~
• 30% số test còn lại ứng với 30% số điểm thỏa mãn: ~n \leq 10^6~ và ~x \leq 10^6~