Lvminh đang làm thêm ở một của hàng tạp hóa. Tại đó có \(N\) sản phẩm lần lượt có giá là \(a_1, a_2, ..., a_n\)

Hôm nay cửa hàng có \(M\) khuyến mại dạng \(V\), \(K\), \(T\) nghĩa là với sản phẩm thứ \(V\) nếu khách hàng mua được đủ \(K\) sản phẩm thì sẽ được khuyến mại thêm \(T\) sản phẩm cùng loại

Vị khách nqson có \(X\) tiền trong tay bước vào cửa hàng và muốn mua được các sản phẩm với tổng giá trị nhiều nhất có thể.

Biết giá trị của sản phẩm bằng với giá của nó. Bạn hãy giúp anh ấy tính xem tổng giá trị đó là bao nhiêu nhé

Input:

• Dòng đầu tiên là hai số nguyên dương \(N\), \(M\) cách nhau bởi 1 dấu cách \((1 \le N, M \le 10^3)\)
• Dòng 2 là \(N\) số nguyên \(a_1, a_2, ..., a_n\) lần lượt là giá của \(N\) sản phẩm cách nhau bởi 1 dấu cách \((1 \le a_i \le 100)\) với \((1 \le i \le N)\)
• \(M\) dòng tiếp theo mỗi dòng là 3 giá trị nguyên \(V\), \(K\), \(T\) cách nhau bởi 1 dấu cách \((0 \le M \le 10^3)\)
• Dòng cuối cùng là số nguyên \(X\) là số tiền nqson cầm vào cửa hàng

Output:

• Một số nguyên duy nhất là kết quả bài toán

Ví dụ

Input

4 4
1 4 2 3
1 2 1 
2 2 1
2 3 2
3 3 1
20

Output

32

Giải thích: nqson sẽ mua được 5 sản phẩm thứ 2 với giá 4 và nhận được 2 khuyến mại. 1 là mua 2 tặng 1, 2 là mua 3 tặng 2 do đó tổng giá trị sẽ là (5+1+2)*4=32

Lưu ý: mỗi sản phẩm chỉ được áp dụng khuyến mại 1 lần