{"code":"mixm","name":"MIXM","description":"Một chuỗi số là một chuỗi kí tự chỉ gồm các chữ số $1,2,\\ldots,9$.\r\n\r\nCó $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$.\r\n\r\n**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. \r\n\r\n\r\n

Input

\r\n\r\n- Dòng đầu chứa hai số nguyên dương $N,M (N \\leq 50, M \\leq 1000)$;\r\n- Dòng thứ $i$ trong số $N$ dòng tiếp theo chứa một \txâ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$).\r\n\r\n

Output

\r\n\r\n- 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.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 2 2\r\n 123 2\r\n 13 10\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n -1\r\n ```\r\n \r\n ??? warning \"Note\" \r\n\r\n Không thể tạo ra số nguyên dương chia hết cho $2$.\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 2 6\r\n 2 20\r\n 77 6\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 32\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Tạo được số nguyên dương $77772$ chi hết cho $6$ với chi phí $6+6+20=32$.","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":512000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}