{"code":"coinsrepay","name":"Trả tiền","description":"Nước Silverland sử dụng hệ thống $100$ loại tiền xu, trong đó các xu có mệnh giá là một số chính phương từ $1^2$ đến $100^2$: \r\nVới hệ thống này, để trả chính xác $10$ xu ta có $4$ cách:\r\n\r\n * Trả $10$ đồng $1$ xu.\r\n * Trả $6$ đồng $1$ xu và $1$ đồng $4$ xu.\r\n * Trả $2$ đồng $1$ xu và $2$ đồng $4$ xu.\r\n * Trả $1$ đồng $1$ xu và $1$ đồng $9$ xu.\r\n\r\nHãy xác định số lượng cách trả chính xác một số tiền $m$ cho trước ở Silverland và đưa ra một cách trả phải **dùng ít đồng xu nhất**.\r\n\r\n\r\n#### Input \r\n* Dòng 1: số nguyên dương $m$ $(m≤10^5 )$.\r\n\r\n#### Output\r\n * Dòng 1 : số nguyên $k$ là số lượng cách trả, lấy phần dư khi chia cho **123456789**;\r\n * Dòng 2: số nguyên $q$ là số đồng xu tối thiểu phải sử dụng để trả;\r\n * Các dòng tiếp theo, mỗi dòng ghi hai số nguyên dương $a,b$ cho biết sử dụng $a$ đồng xu loại mệnh giá $b^2$ trong phương án tối ưu (**dùng ít đồng xu nhất**).\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        19\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        10\r\n        3\r\n        2 3\r\n        1 1\r\n        ```","points":1000.0,"partial":false,"time_limit":1.0,"memory_limit":1048576,"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}}