Sau khi huỷ diệt Weibo Gaming với tỷ số \(3 – 0\), T1 đã chính thức lần thứ tư lên ngôi vô địch chung kết thế giới. \(7\) năm mòn mỏi chờ đợi của các Tcon đã khép lại trong quả ngọt, giờ là lúc để chúng ta cùng chia vui và chứng kiến các tình yêu ngự trị trên ngai vàng thế giới. Riêng với Faker, màn hạ đo ván The Shy là lời tuyên bố rõng rạc và đanh thép: chúa chỉ có \(1\) mà thôi!

Một trong những yếu tố khiến T1 dễ dàng nghiền nát Weibo Gaming là những màn cấm chọn cân não. Với bể tướng khủng của Gumayusi và Keria, họ sẵn sàng chọn cuối để có những lượt lựa chọn khắc chế mạnh, qua đó khiến đối thủ phải chịu thua dù ván đấu chưa diễn ra phút nào. Nhân ngày T1 đăng quang, chúng ta hãy cùng giải một bài toán về việc cấm chọn này nhé.

Lưu ý rằng bài toán này chỉ được lấy ý tưởng từ việc cấm chọn trong bộ môn Liên Minh Huyền Thoại, chứ hoàn toàn không giống với trò chơi thực. Bởi vậy bạn không cần chơi Liên Minh để làm được bài này, mà có chơi nhiều cũng chưa chắc làm được bài toán này đâu nha. À nhưng mà có một điều chắc chắn là, nếu bạn không chơi Liên Minh mà thay vào đó chơi Liên Quân á, thì bạn sẽ không có giải quốc gia đâu hihi. Vì tương lai có giải quốc gia, hãy nói không với Liên Quân nhé!

Bể tướng của Liên Minh Huyền Thoại có \(n\) vị tướng được đánh số từ \(1\) đến \(n\). Vị tướng thứ \(i\) có chỉ số sức mạnh là \(s_{i}\). Đội chọn được tướng có chỉ số sức mạnh cao sẽ càng có lợi thế trong ván đấu. Hai đội, gọi là đội xanh và đội đỏ, tham gia loạt cấm chọn. Trước khi loạt cấm chọn bắt đầu, trọng tài công bố thông tin về loạt cấm chọn: sẽ có tất cả \(m\) lượt chơi, mỗi lượt sẽ được thực hiện bởi một trong hai đội xanh hoặc đỏ, và lượt đó sẽ hoặc là lượt cấm hoặc là lượt chọn. Mỗi lượt chơi thuộc loại nào và do đội nào thực hiện là cố định và được trọng tài thông báo ngay từ đầu. Sau đó, lần lượt các lượt chơi diễn ra. Tại mỗi lượt, đội thực hiện lượt đó đưa ra quyết định cho mình. Luật chơi cụ thể như sau:

• Nếu lượt hiện tại là lượt chọn, đội thực hiện lượt này phải chọn một vị tướng trong \(n\) vị tướng thuộc bể tướng của Liên Minh Huyền Thoại. Vị tướng này sẽ được coi là thuộc về đội thực hiện lượt chọn này.
• Nếu lượt hiện tại là lượt cấm, đội thực hiện lượt này có thể cấm một trong \(n\) vị tướng hoặc không cấm vị tướng nào. Vị tướng bị cấm, nếu có, sẽ không thuộc về bất kỳ đội nào. Việc cấm này chỉ nhằm mục đích ngăn cản đối phương chọn được vị tướng này trong các lượt tiếp theo. Nếu không có vị tướng nào bị cấm, lượt cấm này coi như bị bỏ qua.
• Mỗi vị tướng chỉ được xuất hiện tối đa một lần trong suốt cả loạt cấm chọn. Nói cách khác, nếu một vị tướng đã được chọn hay bị cấm đi bởi một đội nào đó, nó chắc chắn sẽ không thể được chọn hay bị cấm đi bởi bất kỳ đội nào trong tương lai.

Để có được lợi thế trong ván đấu, cả hai đội đều muốn đội mình có được những vị tướng mạnh nhất còn đối phương có được những vị tướng yếu nhất. Nói cách khác, gọi \(B\) là tổng sức mạnh của những vị tướng thuộc về đội xanh, \(R\) là tổng sức mạnh của những vị tướng thuộc về đội đỏ; đội xanh mong muốn giá trị \(B − R\) lớn nhất có thể, đội đỏ cực tiểu hoá giá trị \(B − R\).

Hãy xác định giá trị \(B − R\) sau khi toàn bộ \(m\) lượt chơi của loạt cấm chọn kết thúc, biết rằng cả hai đội đều rất thông minh, đều biết đối thủ rất thông minh, đều biết đối thủ biết mình rất thông minh,...

Input

• Dòng đầu tiên chứa hai số nguyên \(\theta\) và \(\tau\) lần lượt là số thứ tự của subtask chứa test này và số bộ dữ liệu có trong file dữ liệu. Sau đó, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:
  • Dòng đầu tiên là một dòng trống.
  • Dòng thứ hai chứa hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 10^{4}, 1 \leq m \leq 22, m \leq n)\) lần lượt số vị tướng trong bể tướng của Liên Minh Huyền Thoại và số lượt chơi trong loạt cấm chọn.
  • Dòng thứ ba chứa \(n\) số nguyên \(s_{1}, s_{2}, \ldots, s_{n}\) \((1 \leq si \leq 10^{8})\) là sức mạnh của các vị tướng.
  • Trong \(m\) dòng cuối cùng, dòng thứ \(i\) mô tả lượt chơi thứ \(i\) của loạt cấm chọn bởi một chữ cái là b hoặc p và một số nguyên là \(1\) hoặc \(2\). Nếu chữ cái là b, lượt thứ \(i\) là lượt cấm; nếu chữ cái là p, lượt thứ \(i\) là lượt chọn. Nếu số nguyên là \(1\), đội xanh sẽ thực hiện lượt này; nếu số nguyên là \(2\), đội đỏ sẽ thực hiện lượt này.
  • Dữ liệu vào đảm bảo mỗi đội có ít nhất một lượt chọn, số lượt cấm của hai đội bằng nhau và số lượt chọn của hai đội bằng nhau.
• Gọi \(N\) là tổng giá trị của \(n\) trong tất cả các bộ dữ liệu và \(M\) là tổng giá trị của \(m\) trong tất cả các bộ dữ liệu, dữ liệu vào đảm bảo \(N \leq 3 \times 10^{4}\) và \(M \leq 50\).

Output

• Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên duy nhất là giá trị \(B − R\) sau khi loạt cấm chọn kết thúc.

Scoring

• Subtask \(1\) (\(8.4\) điểm): Tất cả các lượt chơi đều là lượt chọn.
• Subtask \(2\) (\(9.8\) điểm): Tất cả \(\dfrac{m}{2}\) lượt chơi đầu tiên đều thuộc về đội xanh.
• Subtask \(3\) (\(14\) điểm): \(s_{i} \leq 5\).
• Subtask \(4\) (\(12.6\) điểm): \(m \leq 4\).
• Subtask \(5\) (\(13.3\) điểm): \(m \leq 16\).
• Subtask \(6\) (\(11.9\) điểm): Không có ràng buộc gì thêm.

Example

4 2

4 4
8 4 1 1
b 1
b 2
p 1
p 2

4 4
13 11 7 5
p 1
p 2
p 2
p 1

3
0