Carmen - một con bò sữa giống {Holsteins} vô cùng quý giá của nông dân John - đã rơi vào một chiếc "giếng rác". Đây là nơi nông dân thường ném rác xuống, và nó có độ sâu là \(D\) (đơn vị: feet, với \(2 \le D \le 100\)).

Carmen muốn chất các mảnh rác lại để tạo thành một đống cao bằng hoặc cao hơn miệng giếng (tức tổng chiều cao đống rác \(\geq D\)), từ đó có thể leo ra ngoài. Ngoài ra, Carmen có thể ăn một số rác để duy trì sự sống.

Mỗi mảnh rác có thể:

• Dùng để {ăn} (tăng thời gian sống),
• Hoặc dùng để {chất đống} (tăng chiều cao),

và việc chất rác không mất thời gian.

Ban đầu Carmen có đủ năng lượng để sống trong 10 đơn vị thời gian. Nếu không ăn thêm gì sau đúng 10 thời gian (không bao gồm thời điểm thứ 10), Carmen sẽ chết đói. Tuy nhiên, nếu đến đúng thời điểm đó mà Carmen kịp ăn rác hoặc leo ra khỏi giếng, thì cô ấy vẫn sống.

Biết trước thời gian mỗi mảnh rác được ném xuống là \(t\) (\(1 \le t \le 1000\)), giá trị năng lượng khi ăn là \(f\) (\(1 \le f \le 30\)), và độ cao có thể chất lên là \(h\) (\(1 \le h \le 25\)), hãy tính thời điểm sớm nhất Carmen có thể thoát khỏi giếng. Nếu không thể thoát, hãy cho biết cô ấy có thể sống được bao lâu.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên: \(D\) và \(G\) - độ sâu giếng và số lượng mảnh rác (\(1 \le G \le 100\)).
• Tiếp theo là \(G\) dòng, mỗi dòng ba số nguyên:
• \(T\) - thời điểm mảnh rác được ném xuống (\(1 \le T \le 1000\)),
• \(F\) - thời gian sống tăng thêm nếu ăn mảnh rác đó (\(1 \le F \le 30\)),
• \(H\) - chiều cao nếu chất mảnh rác đó (\(1 \le H \le 25\)).

Dữ liệu ra

• Một số nguyên:
• Nếu Carmen có thể thoát ra, in ra thời điểm sớm nhất cô ấy có thể ra khỏi giếng.
• Nếu không, in ra thời gian dài nhất cô ấy có thể sống.

Input 1

20 4
5 4 9
9 3 2
12 6 10
13 1 1

Output 1

13

Giải thích mẫu

• Thời điểm 5: Chất rác đầu tiên, chiều cao = 9.
• Thời điểm 9: Ăn rác thứ hai, thời gian sống từ 10 → 13.
• Thời điểm 12: Chất rác thứ ba, chiều cao = 19.
• Thời điểm 13: Chất rác cuối cùng, chiều cao = 20 \(\Rightarrow\) thoát ra được.