There are two parallel conveyor belts pushing, each, a sequence of products of varying value and type. Each conveyor belt can advance as far as you like but cannot move backwards. If, at the edge of the conveyors, there are two compatible products, i.e., two products with the same type, you got a pair and you can take both products together from the conveyor belts. The value of a pair is the sum of the two product values.
For reasons unknown, every product falling from a conveyor without being taken as part of a pair cannot be reused.
Given two product sequences, return the maximum possible value you can take and the minimum number of pairs necessary to achieve it.
The first line is an integer with the number of test samples. For each sample, the next line has the number of products of the first conveyor belt. Then, on each line, from first to last product, comes each product information: product name (a string), product type (an uppercase char) and product value (an integer). The same format follows to describe the products of the second conveyor belt.
For each sample, a line consisting of: the maximum possible value, one space, the minimum number of pairs, a newline.
3 4 nail B 5000 spoon A 1200 orange C 5 nail B 50 3 fork A 50000 hammer B 10 apple C 600 3 zorg X 500 xylf Y 50 krypt Z 450 3 xylf Y 50 tonite Z 450 lum X 500 1 a b 1 0
51805 2 1000 1 0 0
This document was translated from LATEX by HEVEA.