Description

ICPC (International Collegiate Programming Contest), as you might know, is a team programming contest for college students. Each team consists of exactly three students and they will work on a number of programming problems.

Andi, Budi and Chandra plan to participate in this year ICPC as a team. As for their team strategy, they come up with a simple one:

In the first 20 minutes of 5 hours contest, they will read through all problems. Then each of them will assign a number to each problem. This number indicates how many minute(s) it will take for him to get the problem accepted (correct solution). Then they will start to code, meaning that they only have 280 minutes to really work on the problems. You may assume that they always get accepted on time whenever they work on a problem.
There's only one computer for each team, so it's not possible for them to code two different problems simultaneously.
To avoid any brain fatigue and adrenaline rush (because they attend competitions so frequently), they decided to switch role after each problem, such that none of them will work at the computer for more than one problem consecutively.
They want to solve as many problems as they can. The order of problem to be solved does not matter.

Input

The first line of input contains an integer T , number of test cases to follow. Each case begins with an integer N (1N12) in one line, denoting the number of problems. The second line contains N integers, A1..N (1Ai300) , denoting the total time (in minutes) needed by Andi to solve ith problem. The third and fourth line will correspond to the total time needed by Budi and Chandra respectively and will have the same input format as the second line.

Output

For each case, print in a single line containing the maximum total number of problem that can be solved by that team.


Explanation for 1st sample case:

Actually Andi could solve all the three problems alone, but the team has decided that none of them should work at the computer for more than one problem consecutively.


Explanation for 2nd sample case:

The team can solve all the problems. Here is one solution:

Let Budi work on Problem-2 (100 minutes).
Switch to Andi and let him work on Problem-1 (50 minutes).
Switch to Budi again and let him work on Problem-3 (30 minutes).
Finally, switch to Chandra and let him work on Problem-4 which (100 minutes).
Overall, they need 100 + 50 + 30 + 100 = 280 minutes.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Astronomers have been looking for living beings in the outer planets. Recently the Hobble telescope has picked up binary (black and white) images from the Zkrets planet (1 light-years away). Each image contains exactly one symbol. Together the sequence of symbols (images) represents a message for aliens from other planets. A team of deciphering experts has found some decoding scheme that assigns an English alphabet to each symbol. The decoding process would be easy if each received image were in perfect condition. Unfortunately, due to long distance transmission, the images received usually contain some noise, meaning that some white pixels are turned into black pixels and vise versa. Furthermore, due to self-rotation of the Hobble telescope, the images, when captured, might be rotated 0, 90, 180 or 270 degrees. To expedite the message decoding process, please write a program to decode the received sequence of images automatically.


Technical Specification

The number of images received is n, where 1n100 . The size of the image is always scaled to 10×10 . Within the image, `1' represents a black pixel (part of the symbol) and `0' represents a white pixel (not part of the symbol).
Each received image may contain at most 20% noise. This means that at most 20 pixels may have their gray levels changed (from black to white or from white to black) during transmission. Each image is rotated 0, 90, 180 or 270 degrees in clockwise direction.
The number of matching symbols and English Alphabets is m , where 1m52 . The matching English Alphabets can be either upper-case or lower-case letters.

Input

There are two parts of input, one follows the other. For the first part, it contains the matching English alphabets and image symbols. Thus, the first line contains an integer m , the number of matching alphabets and symbols. The next 11m lines define the m sets of matching alphabets and symbols. The first line of each set contains a single unique English letter. The next 10 lines give the matching symbol in a perfect (no noise, no rotation) 10×10 image of 0's and 1's. For the second part, it contains a sequence of received images. The first line contains an integer n , the number of 10×10 images received. The next 10n lines present the n images received. Every 10 lines define one image. Each line contains exactly 10 consecutive 0's and 1's.

Output

Please print out the corresponding English letters of the received input images in sequence, all on one line. If more than one match is possible for a given input image, output the matching one with the least number of noise pixels. If there is still a tie, output the one that appears first in the input sequence of English alphabets.

Explanations for the Sample:

There are 2 deciphered matching codes.
The first is coded as letter a. The corresponding image is giving in 10 rows of consecutive 0's and 1's.

The second image is coded as letter X. The corresponding image is giving in 10 rows of consecutive 0's and 1's.

There are 3 received images waiting to be decoded.
The first received image has 10 rows of consecutive 0's and 1's. It matches with the corresponding image of the coded symbol 'X' perfectly without any noise. The image is either not rotated or perhaps rotated by 180 degrees.

The second image has also 10 rows of consecutive 0's and 1's. It also matches with the corresponding image of the coded symbol 'X' perfectly without any noise. However, the image is either rotated by 90 or 270 degrees.

The third image has also 10 rows of consecutive 0's and 1's. It contains 12 noise pixels. The image is also rotated by 90 degrees. It matches with the corresponding image of the coded symbol 'a'.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two integers A and B that are not necessarily in base-10, find the smallest possible A + B in base-10.

For example,

A = 213, possibly base-4 (39 in base-10)
B = 4721, possibly base-8 (2513 in base-10)
A + B = 39 + 2513 = 2552

Input

First line of the input contains a positive integer T (1 <= T <= 100), the number of cases. Each case contains two positive integers A and B. A and B will contain at most 5 digits, each digit will be between 0 and 9, inclusive, and no leading zeroes.

Output

For each case, output an integer in base-10 denoting the smallest possible A + B.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a sensational scene in the 8-th installment of the Voldemort book series, the robot Weighd was attacked and its rotating top and wings were severely damaged. Weighd cannot rotate its famous top and can only fly forward or make a right-turn. However, the brave Weighd must still navigate a magically created series of mazes to deliver its precious message to Ttoper.

Weighd enters each maze at the top-left square of the maze, takes one unit of time to travel between adjacent squares in the magic maze (forward or right), and cannot stay in one square to rotate itself, and thus change direction, for fear of evil jinx. Your task is to write a program to calculate the smallest number of squares that Weighd must travel to reach a certain square in each maze. Do not you worry about how? Weighd will feel its correct way through the force. Examples are:



Weighd can reach the location marked ``X" of the top maze in ``19" steps, but it cannot reach the marked location in the bottom maze at all.

Input

Input consists of multiple mazes. Each maze description starts with two integers, on a separate line, that represent its dimensions. The first integer N (1<=1000) represents the number of rows and the second M (1<=1000) represents the number of columns. The last maze is followed by a line containing two zeros that indicate the end of the input data and should not be processed as a valid situation.

The second line contains two integers, C (1<=N) and R (1<=M), that represent the column number and the row number of the square where Weighd must reach in the maze. Consecutive integers are separated by a blank space.

Each of the following N lines contains a sequence of 0s and 1s. The sequence is M characters long. The sequence does not contains blank spaces. A value one (1) represents a wall in the maze (that is, a square into which Weighd cannot fly).

Output

Output consists of one line for each maze. It will be in one of the following two formats:

1. an integer that represents the number of steps to be taken, inside the maze, by Weighd to reach its destination.
2. The string ``NOOO!", if no path can be found.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 Lately, there is one serious problem with Panda Land Safe Box: several safes have been robbed! The safes are using old 4-digits rolling lock combination (you only have to roll the digit, either up or down, until all four of them match the key). Each digit is designed to roll from 0 to 9. Rolling-up at 9 will make the digit become 0, and rolling-down at 0 will make the digit become 9. Since there are only 10000 possible keys, 0000 through 9999, anyone can try all the combinations until the safe is unlocked.

• Initially the digits are at 0000.
• Keys can be unlocked in any order, by setting the digits in the lock to match the desired key and then pressing the UNLOCK button.
• A magic JUMP button can turn the digits into any of the unlocked keys without doing any rolling.
• The safe will be unlocked if and only if all the keys are unlocked in a minimum total amount of rolling, excluding JUMP (yes, this feature is the coolest one).
• If the number of rolling is exceeded, then the digits will be reset to 0000 and all the keys will be locked again. In other word, the state of the lock will be reset the cracking is failed.

Input

 The first line of input contains an integer T , the number of test cases follow. Each case begins with an integer N (1≤N≤500) , the number of keys. The next N lines, each contains exactly four digits number (leading zero allowed) representing the keys to be unlocked.

Output

For each case, print in a single line the minimum number of rolls needed to unlock all the keys.

• Turn 0000 into 1111, rolls: 4
• Turn 1111 into 1155, rolls: 8
• Jump 1155 into 1111, we can do this because 1111 has been unlocked before.
• Turn 1111 into 5511 rolls: 8

Sample Input  Download

Sample Output  Download

Tags

Discuss