Một chuỗi số là một chuỗi kí tự chỉ gồm các chữ số \(1,2,\ldots,9\).

Có \(N\) chuỗi số, chuỗi số thứ \(i\) kí hiệu là \(A_i\) và có chi phí khi dùng một lần là \(W_i\). Hay nói cách khác, bài toán này cho phép bạn sử dụng vô số lần, nếu dùng đúng \(T\) lần thì chi phí bạn phải bỏ ra là \(T \times W_i\).

Yêu cầu: Cho một số nguyên dương \(M\). Bạn hãy tìm cách sử dụng \(N\) chuỗi số này và ghép lại theo một thứ tự bất kì và bao nhiêu lần tùy thích để có được một số nguyên dương chia hết cho \(M\) và mất chi phí ít nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(N,M (N \leq 50, M \leq 1000)\);
• Dòng thứ \(i\) trong số \(N\) dòng tiếp theo chứa một xâu gồm các kí tự số \(A_i\) và chi phí \(W_i\) (\(|A_i |\leq 1000, 1\leq W_i \leq 1000\)).

Output

• In ra duy nhất một số nguyên là kết quả tìm được hoặc in ra \(-1\) nếu không có phương án.

Example

2 2
123 2
13 10

-1

2 6
2 20
77 6

32