Cơm lam

Tham gia thi và vui chơi tại Trại hè Hùng Vương xong, trường của Zin chuẩn bị mua món quà về cho học sinh của nhà trường. Sau khi được thầy Vương và cô Tiến tư vấn, trưởng đoàn quyết định mua cho mỗi học sinh một ống cơm lam, có tất cả $S$ học sinh sẽ được nhận quà.

Được biết hiện cơm lam đang bán ở $L$ cửa hàng và tại những cửa hàng này đang thực hiện giảm giá cho những người mua nhiều. Cửa hàng thứ $i$ còn tất cả $F_i$ ống cơm lam, bán với giá $P_i$ đồng/ống cơm lam, tuy nhiên nếu bạn mua ít nhất $R_i$ ống thì bạn được hưởng giá ưu đãi: chỉ phải trả $Q_i$ đồng/ống cơm lam. Nói cách khác, nếu mua $k$ ống ($0\le k\le F_i$) ở cửa hàng thứ $i$ thì số tiền phải trả ở cửa hàng đó là $k·Q_i$ khi $k\ge R_i$ và $k·P_i$ khi $k<R_i$. Mỗi cửa hàng được mua nhiều nhất một lần (mua một lượng $k$ tùy chọn).

Trưởng đoàn chưa biết mua thế nào để mỗi bạn trong $S$ bạn sẽ nhận được một ống cơm lam với tổng tiền phải trả là ít nhất. Bạn là thành viên thi môn Tin học, hãy tư vấn cho thầy trưởng đoàn cách mua theo yêu cầu đặt ra. Bạn nên lưu ý: có thể mua nhiều hơn $S$ ống cơm lam.

Yêu cầu: Hãy tìm số tiền cần thiết nhỏ nhất để mua được ít nhất $S$ ống cơm lam.

Dữ liệu vào

• Dòng 1 ghi hai số nguyên $S$ và $L$ ($1\le S\le 100$, $0\le L\le 100$).
• Mỗi dòng trong $L$ dòng tiếp theo ghi thông tin về cửa hàng thứ $i$ gồm $4$ số nguyên $F_i,P_i,R_i,Q_i$ ($1\le Q_i\le P_i\le 1000$, $1\le R_i\le 100$, $0\le F_i\le 100$).

Dữ liệu ra

In ra một số nguyên duy nhất là số tiền cần thiết nhỏ nhất để mua cơm lam. Nếu cơm lam ở các cửa hàng không đủ để mua thì in ra $-1$.

Ràng buộc

• $1\le S\le 100$, $0\le L\le 100$.
• $1\le Q_i\le P_i\le 1000$, $1\le R_i\le 100$, $0\le F_i\le 100$.

Subtasks

• $40\%$ số test: $P_i=Q_i$ với mọi $i$.
• $40\%$ số test: $F_i=1$ với mọi $i$.
• $20\%$ số test còn lại: không có ràng buộc gì thêm.

Ví dụ