Competition

A logistics company receives N transportation orders 1, 2, . . ., N from a supply location to consumption location in which the order i has weight w(i) and price p(i) (i = 1, 2, . . ., N).

The company has a fleet of K trucks 1, 2, . . ., K in which each truck k has:

• lower bound capacity LQ(k)
• upper bound capacity UQ(k)
• operation cost c(k)

If a truck k operates the transportation activity, total weights of orders it carries must be greater  or equal to the lower bound capacity LQ(k) and less than or equal to the upper bound capacity UQ(k), and the cost is c(k).

The company must select a subset of N orders for serving that assign these selected orders to trucks (each order is assigned to one truck) so that the lower and upper bound capacity constraints on trucks are satisfied and total benefits is maximal.

(the benefit is defined to be the sum of prices of served orders subtract the total cost of trucks used).

Input

• Line 1: contains positive integers N and K (1 <= N <= 10000, 1 <= K <= 1000)
• Line i+1 (i = 1,…, N): contains 2 integers w(i) and p(i)  (1 <= w(i) <= 100, 10 <= p(i) <= 100)
• Line N+1+k (k = 1,…, K): contains 3 integers LQ(k), UQ(k), and c(k)  (1 <= LQ(k) <= UQ(k) <= 1000, 1 <= c(k) <= 50)

Output

• Line 1: contains an integer m
• Line i + 1 (i = 1, 2, . . ., m): contains 2 positive integers i and b in which order i is served by truck b

Example

Input

5 2

5 9

9 2

12 6

12 4

8 6

12 14 5

27 31 8

Output

3

1 2

3 2

4 2

Explanation. 

• There are 5 orders and 2 trucks.
• Orders 1, 3, 4 are served by truck 2. Orders 2, 5 are not served
• Load of truck 1 is: 0 (no order is assigned to truck 1)
• Load of truck 2 is: w(1) + w(3) + w(4) = 5 + 12 + 12 = 29 (which is between 27 and 31: lower and upper bound on capacity is satisfied) 
• Total price of orders served is: p(1) + p(3) + p(4) = 9 + 6 + 4 = 19
• Total cost of trucks used is: c(2) = 8
• Benefit = total price – total cost = 19 – 8 = 11

Restriction:

• Time limit for each testcase is 5 minutes
• Memory limit is 1024MB
• Programming languages: C, C++, Java, Python