{"raw_statement":[{"iden":"statement","content":"You're participating in a contest for finding the 1031415926th prime number. You've developed a relatively fast algorithm, that has been working for a month, to find that number. To maximize the utilization of the resources you have, you distributed the work of the algorithm over k threads, where each thread was assigned a specific amount of work.\n\nTwo days left until the contest deadline, and the only thing you know about the progress of your algorithm is shown on the console window:\n\nThe first line shows the amount of work assigned to each of the k threads, these amounts were assigned randomly (clever!). Each of the following lines has a single integer that represents the current progress of one of the threads. You don't know for which thread each line belongs, but you do know that the progress value of each thread never decreases and doesn't exceed the amount of work assigned to the thread. Each thread takes a non-zero amount of the remaining work assigned to it, finishes it and then reports its new progress, for that no thread will print the same progress value twice, and all the finished work of the threads is reported.\n\nTo have an idea about the actual progress of your algorithm, you want to know the minimum and the maximum possible overall amount of remaining work.\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 space-separated integers n and k (1 ≤ n ≤ 100) (2 ≤ k ≤ 16), the number of lines that shows progress values on your screen, and the number of threads.\n\nThe second line contains k space-separated integers w1, w2, ..., wk (1 ≤ wi ≤ 109), the ith integer represents the amount of work assigned to the ith thread.\n\nEach of the following n lines contains a single integer that represents a progress value printed by one of the threads. The lines are given in the order they were printed in.\n\nIt is guaranteed that the input is valid and matches the problem statement.\n\nThe sum of n overall test cases doesn't exceed 1500.\n\nFor each test case, print a single line with two integers, the minimum and the maximum possible overall amount of remaining work, respectively.\n\n"},{"iden":"input","content":"The first line of input contains a single integer T, the number of test cases.The first line of each test case contains two space-separated integers n and k (1 ≤ n ≤ 100) (2 ≤ k ≤ 16), the number of lines that shows progress values on your screen, and the number of threads.The second line contains k space-separated integers w1, w2, ..., wk (1 ≤ wi ≤ 109), the ith integer represents the amount of work assigned to the ith thread.Each of the following n lines contains a single integer that represents a progress value printed by one of the threads. The lines are given in the order they were printed in.It is guaranteed that the input is valid and matches the problem statement.The sum of n overall test cases doesn't exceed 1500."},{"iden":"output","content":"For each test case, print a single line with two integers, the minimum and the maximum possible overall amount of remaining work, respectively."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n, k \\in \\mathbb{Z} $, with $ 1 \\leq n \\leq 100 $, $ 2 \\leq k \\leq 16 $.  \n- Let $ W = (w_1, w_2, \\dots, w_k) \\in \\mathbb{Z}^k $, where $ w_i \\geq 1 $ is the work assigned to thread $ i $.  \n- Let $ P = (p_1, p_2, \\dots, p_n) \\in \\mathbb{Z}^n $ be the sequence of reported progress values, in order of appearance, with $ 1 \\leq p_j \\leq \\max(W) $, and all $ p_j $ distinct.  \n\n**Constraints**  \n1. Each progress value $ p_j $ corresponds to exactly one thread.  \n2. For each thread $ i $, its progress values (if any) form a non-decreasing sequence, and all values lie in $ [1, w_i] $.  \n3. No thread reports the same progress value twice.  \n4. Each reported progress value $ p_j $ is strictly greater than any prior progress value reported by the same thread.  \n5. The total number of reported progress values is $ n $, and $ n \\leq k $.  \n\n**Objective**  \nCompute:  \n- $ \\text{min\\_remaining} $: the minimum possible total remaining work across all threads.  \n- $ \\text{max\\_remaining} $: the maximum possible total remaining work across all threads.  \n\nLet $ R_i = w_i - \\max(\\{ p_j \\mid p_j \\text{ assigned to thread } i \\} \\cup \\{0\\}) $ be the remaining work for thread $ i $.  \nThen:  \n$$\n\\text{min\\_remaining} = \\min_{\\text{valid assignments}} \\sum_{i=1}^k R_i, \\quad \\text{max\\_remaining} = \\max_{\\text{valid assignments}} \\sum_{i=1}^k R_i\n$$  \nwhere the minimization and maximization are over all injective mappings of the $ n $ progress values to $ n $ distinct threads (with the rest having 0 progress), respecting the non-decreasing and distinct progress constraint per thread.","simple_statement":"You have k threads, each assigned some work. You see n progress reports (each is how much work a thread has done so far). You don’t know which report belongs to which thread. Each thread’s progress never decreases and never exceeds its assigned work. No thread reports the same progress twice.\n\nFind the minimum and maximum possible total remaining work across all threads.","has_page_source":false}