Trong trường mẫu giáo có bạn nhỏ. Thầy giáo Tháo Giầy muốn chia kẹo cho các bạn, yêu cầu mỗi bạn đều phải có kẹo.
Tuy nhiên, các bạn nhỏ cũng hay ghen tị và đưa ra một số yêu cầu. Ví dụ bạn Minh không muốn bạn Hồng có nhiều kẹo hơn mình. Do đó, khi chia kẹo, thầy Tháo Giầy cần thỏa mãn yêu cầu của các bạn nhỏ.
Số kẹo của trường là có hạn, Tháo Giầy muốn biết thầy cần chuẩn bị ít nhất bao nhiêu chiếc kẹo để sao cho mỗi bạn nhỏ đều có kẹo và thỏa mãn tất cả các yêu cầu.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và .
dòng tiếp theo, mỗi dòng chứa 3 số biểu thị các mối quan hệ cần thỏa mãn:
Nếu : Số kẹo của bạn thứ phải bằng số kẹo của bạn thứ .
Nếu : Số kẹo của bạn thứ phải ít hơn số kẹo của bạn thứ .
Nếu : Số kẹo của bạn thứ không được ít hơn số kẹo của bạn thứ .
Nếu : Số kẹo của bạn thứ phải nhiều hơn số kẹo của bạn thứ .
Nếu : Số kẹo của bạn thứ không được nhiều hơn số kẹo của bạn thứ .
Kết quả:
Xuất ra một dòng biểu thị số kẹo tối thiểu thầy Tháo Giầy cần chuẩn bị. Nếu không thể thỏa mãn tất cả yêu cầu, xuất .
