Một dự án phần mềm cần triển khai trong \(𝑛\) tháng đánh số từ 1 tới \(𝑛\). Biết rằng:

• Bắt đầu vào một tháng, dự án có quyền thuê thêm nhân công. Để thuê mỗi nhân công cần một khoản chi phí \(𝐻\) (trả cho nhà tuyển dụng).
• Mỗi nhân công được thuê sẽ được trả một khoản lương \(𝑆\) mỗi tháng kể cả khi không làm việc.
• Kết thúc một tháng, dự án có quyền sa thải nhân công. Để sa thải mỗi nhân công cần trả một khoản chi phí \(𝐷\).
• Không có nhân công nào trước khi dự án bắt đầu. Mỗi tháng \(𝑖\) cần tối thiểu \(𝑎_𝑖\) nhân công. Kết thúc tháng thứ
  \(𝑛\), toàn bộ nhân công phải bị sa thải.

Yêu cầu: Hãy giúp ông giám đốc dự án xây dựng kế hoạch thuê nhân công để dự án được hoàn thành với chi phí
thuê nhân công ít nhất có thể.

Input

• Dòng 1 chứa số tháng \(𝑛\ (1 \leq 𝑛 \leq 4.10^5)\).
• Dòng 2 chứa ba số nguyên dương \(𝐻, 𝑆,𝐷\ (𝐻, 𝑆,𝐷 \leq 10^6)\).
• Dòng 3 chứa \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) \((\forall 𝑖: 𝑎_𝑖 \leq 10^6)\).

Output

• Dòng 1: Ghi chi phí tối thiểu tìm được
• Ghi \(𝑛\) số, số thứ \(𝑖\) là số nhân công làm trong dự án tại tháng thứ \(i\).

Scoring

• Subtask \(1\) (\(22.5\%\) số điểm): \(𝑛 \leq 400\).
• Subtask \(2\) (\(40\%\) số điểm): \(𝑛 \leq 10^4\).
• Subtask \(3\) (\(37.5\%\) số điểm): \(𝑛 \leq 4 \times 10^5\).

Example

3
4 5 6
10 9 11 

265
10 10 11

Cho một hình chữ nhật có \(N\) hàng và \(M\) cột có số thứ tự được đánh từ trên xuống và từ trái sang phải.

Trên mỗi ô có viết một số nguyên và nhiệm vụ chúng ta phải trả lời \(Q\) truy vấn. Mỗi truy vấn sẽ gồm bốn số nguyên là \(x_1, y_1, x_2, y_2\), sẽ mô tả một khu vực con trong hình chữ nhật. Ứng với mỗi truy vấn, hãy in ra tổng của của khu vực con đó, có điểm \((x_1, y_1)\) là ô góc trái trên và có điểm \((x_2, y_2)\) là ô ở góc phải dưới của khu vực.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) (chiều rộng) và \(M\) (chiều dài) \((1 \leq N, M \leq 1000)\)
• \(N\) dòng sau, mỗi dòng chứa \(M\) số nguyên, giá trị tuyệt đối của mỗi số nguyên này không vượt quá \(10^9\)
• Dòng kế tiếp, chứa một số nguyên \(Q\) (số truy vấn) \((1 \leq Q \leq 10^5)\)
• \(Q\) dòng kết tiếp, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\). \((1 \leq x_1 \leq x_2 \leq N)\), \((1 \leq y_1 \leq y_2 \leq M)\)

Output

• In ra \(Q\) dòng, ứng với truy vấn thứ \(i\), in ra một số nguyên là tổng của khu vực hình chữ nhật được nhắc đến bởi truy vấn thứ \(i\).

Example

Test 1

Input

3 3
1 2 3
-4 -5 -6
7 8 9
4
1 1 2 3
2 3 3 3
1 1 2 2
1 1 1 3

Output

-9
3
-6
6

Note

Có \(N\) đứa trẻ muốn đi chơi vòng đu quay, và nhiệm vụ của bạn là tìm cáp treo cho mỗi đứa trẻ.

Một cáp treo có thể chứa được \(1\) hoặc \(2\) đứa trẻ, trong đó, tổng trọng lượng mỗi cáp treo không được vượt quá \(x\). Bạn biết trọng lượng của mỗi đứa trẻ.

Hỏi số cáp treo ít nhất cần để chở hết tất cả đứa trẻ là bao nhiêu?

Input

• Dòng đầu tiên chứa \(2\) số tự nhiên \(N\) và \(x\) - Số lượng đứa trẻ và tổng trọng lượng tối đa cho phép.
• Dòng tiếp theo chứa \(N\) số tự nhiên \(p_1, p_2, p_3, \ldots ,p_N\) - trọng lượng của mỗi đứa trẻ.

Output

• In ra số lượng cáp treo tối thiểu.

Constraints

• \(1 \leq N \leq 2 * 10^5\).
• \(1 \leq p_i \leq x \leq 10^9\).

Sample Test

Input:

4 10
7 2 3 9

Output:

3