Cắt xâu số thành K phần

Cô giáo đưa cho hai bạn Nam và Bình một xâu \(s\) chỉ gồm các chữ số \(0\)–\(9\) và đặt bài toán: hãy cắt xâu thành đúng \(K\) đoạn liên tiếp (mỗi đoạn không rỗng, mỗi ký tự thuộc đúng một đoạn) sao cho giá trị số của mỗi đoạn không vượt quá \(Z\). Đoạn được hiểu là số nguyên thập phân và có thể có chữ số \(0\) ở đầu (ví dụ 07 có giá trị \(7\)).

Trong tất cả các cách cắt hợp lệ, hãy chọn cách sao cho tổng giá trị của \(K\) đoạn là lớn nhất. Nếu không có cách cắt nào hợp lệ, in ra \(-1\).

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ test.
• Mỗi bộ test gồm hai dòng: dòng đầu chứa hai số nguyên \(K\) và \(Z\); dòng thứ hai chứa xâu \(s\).

Output

Với mỗi bộ test in ra một dòng là tổng lớn nhất, hoặc \(-1\) nếu không thể cắt.

Constraints

• \(1 \le T \le 10\)
• \(1 \le K \le 100\), \(1 \le Z \le 10^9\)
• \(1 \le |s| \le 100\), \(s\) chỉ gồm các ký tự từ 0 đến 9

Sample Input

3
2 50
4817
1 20
123
3 100
90210

Sample Output

65
-1
111

Explanation

Bộ test 1: cắt 48|17, tổng \(65\). Bộ test 2: chỉ có thể lấy cả xâu là \(123 > 20\) nên không hợp lệ. Bộ test 3: cắt 90|21|0, tổng \(111\).