{"problem":{"name":"G. Notes","description":{"content":"_Jordanian notes are 1, 5, 10, 20, and 50 JDs._ Maram is going to the shop and has N JDs, she wants to have the money in a form that will allow her to pay for any single item exactly, which means wit","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10110G"},"statements":[{"statement_type":"Markdown","content":"_Jordanian notes are 1, 5, 10, 20, and 50 JDs._\n\nMaram is going to the shop and has N JDs, she wants to have the money in a form that will allow her to pay for any single item exactly, which means without waiting for change. Given N and the price of each item in the shop, find the required form, that is, find the number of notes of each type she has to have before going to the shop.\n\nThe first line of input contains a single integer T, the number of test cases.\n\nThe first line of each test case contains two integers N and M (1 ≤ N, M ≤ 105), the amount of money Maram has and the number of items in the shop, respectively. The second line contains M space-separated integers, each value represents the price of an item and is between 1 and N.\n\nFor each test case, print five space-separated integers on a single line, where the first integer represents the number of notes of the first type (1 JD), the second integer represents the number of notes of the second type (5 JDs), and so on.\n\nIf there’s more than one possible form, find the one that minimizes the total number of notes.\n\nNote that the total amount of money in the printed form should be equal to N.\n\n## Input\n\nThe first line of input contains a single integer T, the number of test cases.The first line of each test case contains two integers N and M (1 ≤ N, M ≤ 105), the amount of money Maram has and the number of items in the shop, respectively. The second line contains M space-separated integers, each value represents the price of an item and is between 1 and N.\n\n## Output\n\nFor each test case, print five space-separated integers on a single line, where the first integer represents the number of notes of the first type (1 JD), the second integer represents the number of notes of the second type (5 JDs), and so on.If there’s more than one possible form, find the one that minimizes the total number of notes.Note that the total amount of money in the printed form should be equal to N.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ \\mathcal{C} = \\{1, 5, 10, 20, 50\\} $ be the set of Jordanian banknote denominations, indexed in increasing order.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the total amount of money (in JDs).  \n- Let $ M \\in \\mathbb{Z} $ be the number of items.  \n- Let $ P = \\{p_1, p_2, \\dots, p_M\\} \\subseteq \\{1, 2, \\dots, N\\} $ be the set of item prices.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 10^5 $  \n2. For each test case:  \n   - $ 1 \\le N \\le 10^5 $  \n   - $ 1 \\le M \\le 10^5 $  \n   - $ 1 \\le p_i \\le N $ for all $ i \\in \\{1, \\dots, M\\} $  \n\n**Objective**  \nFind a 5-tuple $ (x_1, x_2, x_3, x_4, x_5) \\in \\mathbb{Z}_{\\ge 0}^5 $ such that:  \n$$\n\\sum_{i=1}^{5} x_i \\cdot c_i = N \\quad \\text{where } c_i \\in \\mathcal{C}\n$$  \nand for every price $ p \\in P $, there exists a subset of the selected notes summing exactly to $ p $ (i.e., the note multiset is *universal* for $ P $).  \n\nAmong all such tuples, minimize the total number of notes:  \n$$\n\\min \\sum_{i=1}^{5} x_i\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10110G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}