Problem Description
Given some cards each assigned a number, you're required to select EXACTLY K cards among them.
While you select a card, I will check the number assigned to it and see if it satisfies some of the following conditions:
1. the number is a prime number;
2. the amount of its divisors is a prime number;
3. the sum of its divisors is a prime number;
4. the product of all its divisors is a perfect square number. A perfect square number is such a kind of number that it can be written as a square of an integer.
The score you get from this card is equal to the amount of conditions that its number satisfies. The total score you get from the selection of K cards is equal to the sum of scores of each card you select.
After you have selected K cards, I will check if there's any condition that has never been satisfied by any card you select. If there is, I will add some extra scores to you for each unsatisfied condition. To make the game more interesting, this score may be negative.
After this, you will get your final score. Your task is to figure out the score of each card and find some way to maximize your final score.
Note that 1 is not a prime number. In this problem, we consider a number to be a divisor of itself. For example, considering the number 16, it is not a prime. All its divisors are respectively 1, 2, 4, 8 and 16, and thus, it has 5 divisors with a sum of 31 and a product of 1024. Therefore, it satisfies the condition 2, 3 and 4, which deserves 3 points.
Input
The first line of the input contains the number of test cases T.
Each test case begins with two integers N and K, indicating there are N kinds of cards, and you're required to select K cards among them.
The next N lines describes all the cards. Each of the N lines consists of two integers A and B, which denote that the number written on this kind of card is A, and you can select at most B cards of this kind.
The last line contains 4 integers, where the ith integer indicates the extra score that will be added to the result if the ith condition is not satisfied. The ABSOLUTE value of these four integers will not exceed 40000.
You may assume 0<N≤103,0<K≤104,1≤A≤106,1≤B≤104,T≤40 and the total N of all cases is no more than 20000. In each case there are always enough cards that you're able to select exact K cards among them.
Output
Output two lines for each test case.
The first line consists of N integers separated by blanks, where the ith integer is the score of the ith card.
The second line contains a single integer, the maximum final scores you can get.
Sample Input
1
5 3
1 1
2 1
3 1
4 1
5 1
1 2 3 4
Sample Output
1 3 2 2 2
11
