Công ty HP có hai tổ hoàn thiện sản phẩm, tổ ~1~ có ~m~ công nhân, tổ ~2~ có ~n~ công nhân. Giám đốc yêu cầu ~2~ tổ phải hoàn thiện ~m + n~ sản phẩm sao cho:

• Mỗi công nhân phải hoàn thiện ~1~ sản phẩm;
• Sản phẩm ~i~ ~(1 \le i \le m + n)~ nếu giao cho tổ ~1~ hoàn thiện mất ~a_i~ giây, nếu giao cho tổ ~2~ hoàn thiện thì mất ~b_i~ giây.
• Một số sản phẩm chỉ có thể giao cho tổ ~1~ hoàn thiện, ngược lại một số sản phẩm chỉ có thể giao cho tổ ~2~ hoàn thiện.

Yêu cầu

Bạn hãy giúp giám đốc công ty giao việc cho các công nhân ~2~ tổ sao cho tổng thời gian hoàn thiện ~m + n~ sản phẩm của các công nhân là nhỏ nhất.

Dữ liệu đầu vào

Gồm ~m + n + 1~ dòng:

• Dòng đầu tiên ghi hai số nguyên dương ~m,\ n~ ~(1 \le m, n \le 10^5)~;
• ~m + n~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le m + n)~ là ba số ~a_i, b_i, c_i~ ~(1 \le a_i, b_i \le 10^6)~:
  • ~c_i = 0~ sản phẩm ~i~ có thể hoàn thiện bởi công nhân của cả ~2~ tổ;
  • ~c_i = 1~ sản phẩm ~i~ chỉ được hoàn thiện bởi công nhân tổ ~1~;
  • ~c_i = 2~ sản phẩm ~i~ chỉ được hoàn thiện bởi công nhân tổ ~2~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là tổng thời gian ít nhất để hoàn thiện ~m + n~ sản phẩm. Dữ liệu vào đảm bảo luôn hoàn thiện ~m + n~ sản phẩm.

Ràng buộc dữ liệu

• 15% số điểm có ~m = 1, n = 1~;
• 15% số điểm có ~c_i \ne 0~ ~(\forall\ i: 1 \le i \le m + n)~;
• 40% số điểm có ~1 < m, n \le 10~.

Ví dụ

Ví dụ 1

INPUT

1 1
9 8 0
7 8 0

OUTPUT

15

Giải thích:

• Tổ ~1~ hoàn thiện sản phẩm ~2~ hết ~7~ giây;
• Tổ ~2~ hoàn thiện sản phẩm ~1~ hết ~8~ giây;

Tổng thời gian hoàn thiện ~2~ sản phẩm là ~7 + 8 = 15~ giây.

Ví dụ 2

INPUT

2 3
5 2 0
8 5 1
1 6 2
1 5 0
2 9 0

OUTPUT

23

Giải thích:

• Tổ ~1~ hoàn thiện sản phẩm ~2~ và ~5~ hết ~8 + 2 = 10~ giây;
• Tổ ~2~ hoàn thiện sản phẩm ~1, 3~ và ~4~ hết ~2 + 6 + 5 = 13~ giây;

Tổng thời gian hoàn thiện ~5~ sản phẩm là ~10 + 13 = 23~ giây.