Game kinh doanh, một trò chơi mới và được giới trẻ yêu thích. Người tham gia trò chơi được cung cấp một số T tiền ban đầu trong tài khoản và được phép kinh doanh trên n mặt hàng. Trò chơi diễn ra trong R lượt, trong mỗi lượt người chơi được phép mua bán các mặt hàng nhằm thu về nhiều lợi nhuận nhất. Cụ thể, mỗi lượt, giá của từng mặt hàng được công bố và người chơi được phép mua bán như sau:

• Mua hàng: Nếu muốn mua \(s_i\) đơn vị mặt hàng thứ \(i\), người chơi phải trả ngay lập tức tiền mua hàng. Số tiền trong tài khoản của người chơi ngay lập tức sẽ bị trừ đi một lượng là \((s_i \times (P_i + d))\) đồng, trong đó \(P_i\) là giá mặt hàng thứ \(i\), \(d\) là phí phụ thêm khi mua một đơn vị hàng. Số lượng hàng mua ngay lập tức sẽ được chuyển vào kho. Số lượng mặt hàng \(i\) trong kho không được phép vượt quá \(C_i\).
• Bán hàng: Nếu người chơi đang có mi đơn vị mặt hàng \(i\) thì người chơi có thể tiến hành bán \(s_i\) \((0 \leq s_i \leq m_i)\) đơn vị mặt hàng. Số tiền bán hàng \((s_i × (P_i - e))\) sẽ được chuyển vào tài khoản của người chơi ngay lập tức, trong đó \(P_i\) là giá mặt hàng thứ \(i\), \(e\) là phí phụ thêm khi bán một đơn vị hàng. Số lượng hàng thứ \(i\) trong kho còn lại là \((m_i – s_i)\).

Yêu cầu: Hãy giúp người chơi tìm cách mua bán hàng để tổng lượng tiền thu được là lớn nhất.

Input

• Dòng đầu chứa \(5\) số nguyên không âm \(n, T, R, d, e\) \((T \leq 10^9; d, e \leq 10^6)\);
• Dòng thứ hai chứa \(n\) số nguyên dương \(C_1, C_2,…, C_n\) cho biết số lượng tối đa của từng mặt hàng được phép chứa trong kho \((C_i \leq 20, i = 1, 2,…, n)\);
• Dòng thứ \(k\) trong \(R\) dòng tiếp theo chứa n số nguyên dương cho biết giá của \(n\) mặt hàng tại lượt thứ \(k\), các số có giá trị không vượt quá \(10^6\).

Output

• Ghi một số nguyên dương duy nhất là tổng lượng tiền người chơi có được sau \(R\) lượt theo cách mua bán hàng tìm được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(𝑛 = 3; 𝑅 \leq 5\);
• Subtask \(2\) (\(25\%\) số điểm): \(𝑛 \leq 5; 𝑅 \leq 5\);
• Subtask \(3\) (\(25\%\) số điểm): \(𝑛 \leq 5; 𝑅 \leq 500; 𝑑 = 𝑒 = 0\).

Example

3 2 2 1 0
1 1 1
1 1 1
2 3 4

4