Given two vectors, compute the sum of the corresponding elements and find the largest component. For example, the sum of [1,2,-3] and [4,5,6] is [5, 7, 3], and the largest component is 7.
We may represent a high-dimensional sparse vector using the following format:
dim1:value1 dim2:value2 dim3:value3 … 0:0
where 0:0 denotes the end of the vector.
Here is an example: The vector [0,5,0,0,9,0,0,33] is an eight-dimensional vector, which can be represented as
2:5 5:9 8:33 0:0
That is, we may omit all dimensions whose values are zero. Such a representation is compact and particularly suitable for high-dimensional sparse vectors.
The input has two lines. Each line contains a vector of integer values represented in the sparse format. The dimension of the vector is no greater than 2 to the 31st power. The usage of memory is limited to 32 MB.
The output is the largest component of the sum of the two input vectors. The answer should be printed in one line with a newline character at the end.
There is a newline in the end.