https://drive.google.com/file/d/1ejzFs65qEhne0CliyAbhUjcf_xWsANOa/view?usp=sharing

Linh là một bạn học sinh giỏi và chấp hành nghiêm chỉnh luật giao thông. Mỗi buổi sáng, Linh sẽ đi từ nhà đến trường trên một tuyến đường cố định mà bạn thích.

Trên tuyến đường này, Linh phải đi qua \(n\) nút giao thông. Các nút giao thông được đánh số lần lượt \(1, 2, 3, \ldots, n\). Thời gian để di chuyển từ nút giao thông \(i\) \((1 \le i <n)\) đến trước nút giao thông \(i+1\) là \(t_i\) giây. Ngoài ra, thời gian để Linh từ nhà đến nút \(1\) và từ nút \(n\) đến trường là không đáng kể (xem như bằng \(0\)), nhưng Linh vẫn phải chờ đèn đỏ tại nút \(n\) trước khi đến trường nếu có.

Mỗi nút giao thông đều có đèn tín hiệu, đèn tín hiệu tại nút giao thông thứ \(j\) \((1 \le j \le n)\) có \(r_j\) giây đèn đỏ và \(g_j\) giây đèn xanh. Tại thời điểm \(0\), đèn tín hiệu ở nút \(j\) vừa chuyển sang màu \(c_j\).

Ngày hôm nay, Linh cần mua \(k\) món đồ trước khi đến trường, các món đồ cũng được đánh số \(1, 2, \ldots, k\). Trước mỗi nút giao thông có một cửa hàng tiện lợi. Do đó, Linh sẽ dừng lại và mua đồ tại một số cửa hàng dọc đường.

Cửa hàng tại nút giao thông thứ \(j\) bán một vài trong \(k\) món đồ mà Linh cần mua (có thể không bán món nào mà Linh cần) và nếu Linh dừng lại mua đồ ở đây sẽ mất \(p_j\) giây. Lưu ý rằng Linh dừng lại mua đồ trước rồi mới di chuyển đến nút giao thông tương ứng, nếu tại thời điểm mua xong mà đèn tín hiệu chuyển đỏ, Linh vẫn phải chờ đèn chuyển xanh rồi mới tiếp tục đi.

Hãy xác định thời điểm sớm nhất mà Linh có thể đến trường và mua hết \(k\) món đồ. Biết rằng mỗi món đồ được bán tại ít nhất một trong các cửa hàng dọc đường đến trường của cô ấy.

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(k\) \((1 \le n \le 10^5, 0 \le k \le 5)\) lần lượt là số nút giao thông trên đường đến trường của Linh và số món đồ Linh cần mua.
• Dòng tiếp theo gồm \(n-1\) số nguyên \(t_1, t_2, \ldots, t_{n-1}\) \((1 \le t_i \le 10^9)\) là thời gian di chuyển giữa các nút giao thông kề nhau.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(r_i\), \(g_i\) và kí tự \(c_i\) \((1 \le r_i, g_i\le 10^9, c_i \in \{\tt{R}, \tt{G}\})\) lần lượt là số giây đèn đỏ, số giây đèn xanh và màu của đèn tại thời điểm \(0\), \(c_i=\tt{R}\) cho biết đèn màu đỏ, \(c_i = \tt{G}\) cho biết đèn màu xanh.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) có dạng:
  • Đầu tiên là số nguyên \(p_i\) \((1 \le p_i \le 10^9)\) cho biết thời gian nếu mua đồ tại cửa hàng ở nút giao thông \(i\).
  • Tiếp theo là số nguyên \(s_i\) \((0 \le s_i \le k)\) cho biết số món đồ ở cửa hàng mà Linh cần, theo sau là \(s_i\) số nguyên là số thứ tự của các món đồ được bán theo thứ tự tăng dần.

Output

• Gồm một dòng duy nhất ghi thời điểm sớm nhất Linh đến trường và mua đủ các món đồ cần thiết.

Ví dụ

Input 1

4 0
1 2 3
1 1 R
1 2 G
2 1 R
2 2 G
1 0
1 0
1 0
1 0

Output 1

8

Chú thích

• Linh đến nút giao thông \(1\) vào thời điểm \(0\). Sau đó, bạn chờ đèn đỏ \(1\) giây, đến nút giao thông \(2\) mất \(1\) giây. Sau đó, bạn chờ đèn đỏ mất \(1\) giây, rồi di chuyển đến nút \(3\) trong \(2\) giây. Khi này đèn tại nút \(3\) vừa chuyển xanh, Linh di chuyển đến nút \(4\) trong \(3\) giây. Tại nút \(4\), đèn vừa chuyển xanh nên Linh có thể đi qua và đến trường tại thời điểm \(1+1+1+2+3 = 8\) giây.

Input2

4 1
1 2 3
1 1 R
1 2 G
2 1 R
2 2 G
4 1 1
3 1 1
2 0
1 1 1

Output 2

9

Giải thích

• Linh đến nút \(4\) sau \(8\) giây tương tự như ví dụ 1, mua món đồ cần mua tại nút \(4\) mất \(1\) giây. Khi đó đèn vẫn còn \(1\) giây xanh nên Linh có thể đến trường vào thời điểm \(9\).

Input 3

4 3
1 2 3
1 1 R
1 2 G
2 1 R
2 2 G
4 2 2 3
3 1 2
2 1 3
1 2 1 3

Output

12

Ràng buộc

• Subtask \(1\) (\(26\%\) số điểm): \(k = 0\).
• Subtask \(2\) (\(28\%\) số điểm): \(k = 1\).
• Subtask \(3\) (\(46\%\) số điểm): Không có ràng buộc gì thêm.