KGMSOCKETS - Mạng lưới điện
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: natsukagami

Bò Bessie rất thích nghịch điện!
Một buổi sáng, bò Bessie được nhận một món quà: một bảng mạch điện! Bảng mạch gồm 1 nguồn và N dây nối ngang song song, dẫn điện 1 trong 2 chiều từ trái sang phải hoặc ngược lại. Đồng thời bảng mạch cũng bao gồm M bóng đèn. Bóng đèn thứ i sẽ được nối vào các dây dẫn liên tiếp từ Li đến Ri và chỉ nhận điện theo 1 chiều. Tuy vậy, do bóng đèn là loại nhỏ nên trong các dây được nối với bóng đèn, chỉ cần 1 dây có cùng chiều điện với bóng đèn là bóng sẽ sáng chói!
Bessie lập tức nối tất cả các bóng đèn vào mạch, và nhanh chóng tìm cách làm cho tất cả bóng đèn đều sáng. Bessie nhận ra mình có thể đảo chiều điện của 1 số dây, việc đảo chiều dây thứ i sẽ mất chi phí là Ci . Hãy xác định giúp Bessie chi phí nhỏ nhất để làm cho tất cả bóng đèn đều sáng!


Dữ liệu vào
• Dòng đầu tiên gồm 2 số N và M (1 ≤ N ≤ 2000, 0 ≤ M ≤ 5000)
• Dòng tiếp theo gồm N kí tự mô tả chiều dòng điện của N dây dẫn (L là sang trái, R là sang phải)
• Dòng tiếp theo gồm N số Ci là chi phí đảo chiều của từng dây dẫn. (1 ≤ Ci ≤ 1000)
• M dòng tiếp theo mô tả các bóng đèn. Mỗi dòng có dạng Li Ri Ki trong đó Ki chỉ chiều điện mà
bóng đèn nhận (L là sang trái, R là sang phải) (1 ≤ Li ≤ Ri ≤ N )


Kết quả ra
• Một dòng duy nhất in ra đáp số của bài.
• Nếu Bessie không thể làm cho tất cả bóng đèn sáng, in −1.

 

Ví dụ

  • input
    2 2
    LL
    2 6
    1 2 L
    1 2 R
    output
    2
  • input
    2 2
    LL
    2 6
    2 2 L
    2 2 R
    output
    -1

Ở test 1 có thể đảo chiều dây thứ nhất.

Back to Top