Hôm nay Hạo rất vui vì gia đình sắp nhận chìa khóa căn nhà mới. Trong đó có một căn phòng rộng rãi dành riêng cho cậu. Điều khiến cậu càng vui hơn là mẹ cậu nói: "Phòng của con muốn mua gì, bố trí thế nào tuỳ con quyết định, miễn sao tổng chi tiêu không vượt quá \(n\) đồng là được."

Ngay sáng hôm sau, Hạo bắt đầu lập kế hoạch mua sắm. Cậu phân loại các món đồ muốn mua thành hai loại: {chính} và {phụ}. Đồ phụ là món đi kèm với một món đồ chính nào đó. Dưới đây là một vài ví dụ:

Để mua một món phụ, bắt buộc phải mua món chính mà nó đi kèm. Mỗi món chính có thể có \(0, 1\) hoặc \(2\) món phụ. Mỗi phụ kiện chỉ gắn với một món chính, và không có phụ kiện nào có thêm phụ kiện riêng.

Do mong muốn mua rất nhiều thứ, Hạo nhận ra tổng chi phí có thể vượt quá số tiền mẹ cho. Vì vậy, cậu gán cho mỗi món đồ một {độ quan trọng} từ \(1\) đến \(5\) (\(5\) là quan trọng nhất). Ngoài ra, cậu còn tra giá tiền của mỗi món trên mạng (đều là bội số của \(10\)).

Mục tiêu của Hạo là: {với số tiền không vượt quá \(n\), chọn mua các món sao cho tổng giá trị (giá tiền × độ quan trọng) là lớn nhất có thể.}

Giả sử món thứ \(j\) có giá \(v_j\), độ quan trọng \(w_j\), nếu chọn \(k\) món có chỉ số \(j_1, j_2, \ldots, j_k\), thì tổng giá trị là: \[ v_{j_1} \times w_{j_1} + v_{j_2} \times w_{j_2} + \dots + v_{j_k} \times w_{j_k} \]

Bạn hãy giúp Hạo chọn ra danh sách mua sắm hợp lý nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên: tổng số tiền \(n\) và số lượng món đồ muốn mua \(m\).
• Dòng thứ \(2\) đến dòng thứ \(m+1\), mỗi dòng gồm ba số nguyên \(v_i\), \(p_i\), \(q_i\):
• \(v_i\): giá tiền của món đồ thứ \(i\) (bội số của 10),
• \(p_i\): độ quan trọng của món thứ \(i\) (1 đến 5),
• \(q_i\): nếu \(q_i = 0\), đây là món chính; ngược lại, nó là phụ kiện của món chính thứ \(q_i\).

Dữ liệu ra

• Một dòng duy nhất chứa một số nguyên — tổng giá trị lớn nhất có thể đạt được.

Ràng buộc dữ liệu

• \(1 \leq n \leq 32\,000\)
• \(1 \leq m \leq 60\)
• \(0 \leq v_i \leq 10\,000\)
• \(1 \leq p_i \leq 5\)
• \(0 \leq q_i \leq m\)
• Đáp án không vượt quá \(200\,000\)

Input 1

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

Output 1

2200