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.

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 lam".

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

Input

• Dòng 1 ghi 2 số ~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ố ~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~).

Output

• Ghi 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ì ghi giá trị -1.