The Dystopian government has installed a giant fountain in front of the parliament building. The fountain consists of N levels stacked one on top of the other and is situated on top of a large tank of infinite capacity. The levels of the fountain are numbered 1 to N from top to bottom. The top l₁ levels are identical with capacity c₁, the next l₂ levels identical with capacity c₂,... the final l_K levels with capacity c_K. Here l₁ + l₂ + ... l_K = N.

When water is added to level i beyond its capacity, the excess water overflows to level i+1. Water overflowing from level N is collected in the tank. Water is added to the levels in the following fashion. First, w₁ amount of water is added to each level i such that s₁ ≤ i ≤ e₁. Then w₂ amount of water is added to each s₂ ≤ i ≤ e₂... Finally w_M amount is added to s_M ≤ i ≤ e_M. Note that water might be added to the same level multiple times in this fashion. You have to find out the amount of water that has overflowed to the tank at the bottom, and the total number of levels of the fountain that are completely filled

Input

The first line of the input contains T (≤10), the number of test cases. Following this are the descriptions of the test cases.

The first line of the description of a test case contains space separated integers N (≤2x10⁸), K (≤2000) and M (≤10⁴). Following this are K lines, each containing a space separated pair of integers. These are the (l_i,c_i) pair as explained in the problem statement. Here l₁ + l₂ + ... l_K = N and c_i ≤ 10⁸. This is followed by M lines, each containing a space separated triplet of integers. These are (s_i,e_i,w_i) as explained in the problem statement. 1 ≤ s_i ≤ e_i ≤ N and w_i ≤ 10⁶

Output

For each test case output a space separated pair of integers : The total amount of water that has overflowed to the tank and the number of levels of the fountain that are completely filled.

Example

Input:
1
10 2 1
5 6
5 3
3 9 5

Output:
5 5