Memory Restoration

In this problem, you are given n memories. The i-th memory consists of a string \(S_i\) (with length not exceeding 100), a depth \(r_i\) representing how deep it is stored in the mind, and a value \(v_i\).

Wenzhaoxue wishes to recall beautiful memories. However, due to the vast number and complexity of these memories, she only remembers a prefix string \(Q\) and is able to reach up to a certain depth \(d\). Only those memories with \(S_i\) having \(Q\) as prefix and with \(r_i \le d\) can be recalled.

You are given m queries. For each query, determine the sum of the values \(v_i\) of all memories that satisfy:

• \(Q\) is a prefix of \(S_i\).
• \(r_i \le d\).

inputFormat

The first line contains two integers n and m, denoting the number of memories and the number of queries respectively.

The following n lines each contain a string \(S_i\), an integer \(r_i\), and an integer \(v_i\), separated by spaces.

The next m lines each contain a string \(Q\) and an integer \(d\), representing a query.

outputFormat

For each query, output a single integer which is the sum of the memory values \(v_i\) for all memories satisfying the given conditions.

sample

4 3
abc 5 10
ab 3 9
a 2 8
abcd 4 7
ab 5
abc 4
a 2

26
7
8