Hiện nay trên internet có hàng tá game như thế này.

Game trong hình có tên là Clone run. Bạn cần đi qua các cửa, mỗi cửa sẽ có 2 lựa chọn với các phép toán cộng, trừ, nhân hay chia số clone của bạn với một số lượng tùy thuộc vào phép tính và con số trên cánh cửa. Mục tiêu của trò chơi là bạn cần đi sao cho số lượng clone của bạn là lớn nhất có thể.

Vì quá chán nên bạn quyết định làm một con bot tự động chơi thay cho bạn.

Lưu ý:

• Số lượng clone không thể là số âm. Vậy nên nếu số lượng clone bị giảm xuống số âm, ta xem như bằng 0.
• Số lượng clone không thể là số thập phân nên khi chia ta chỉ lấy phần nguyên. VD: ~5/2 = 2~

Input

Định dạng đầu vào như sau:

X N
a1 b1 c1 d1
a2 b2 c2 d2
...
aN bN cN bN

• Dòng đầu tiên gồm hai số ~X~ là số clone bạn bắt đầu, ~N~ là số lượng cửa bạn cần đi qua.
• ~N~ dòng tiếp theo, mỗi dòng chứa thông tin của hai cửa bạn cần đi qua là ~a_i, b_i, c_i, d_i~
  • ~a_i, c_i~ là phép tính +, -, *, / (~a_i~ là cửa trái, ~c_i~ là cửa phải)
  • ~b_i, d_i~ là số nguyên (~b_i~ là cửa trái, ~d_i~ là cửa phải)

Output

• Một dòng duy nhất chứa một số là số lượng clone nhiều nhất bạn có thể lấy được.

Giới hạn

• ~1 \le N \le 1000~
• ~0 \le X \le 1000~
• ~-1000 \le a_i, c_i \le 1000~
• ~a_i, c_i \neq 0~ nếu phép tính của cửa đó là phép chia
• Bộ test đảm bảo kết quả không vượt quá kiểu dữ liệu long long (in64_t)

Sample

Input #1

1 4
+ 3 + 5
- 6 - 7
+ 3 + 10
* 5 * 9

Output #1

90

Giải thích #1: