9600: Christmas Tree

There are $n$ light bulbs on the Christmas tree, connected by $(n-1)$ wires. Each wire connects two different bulbs, forming a tree rooted at the $1$-st bulb. Initially, the beauty of the Christmas tree is $0$, and you can light up some bulbs to increase the beauty.

Lighting up the $i$-th bulb consumes aia_iai units of power and increases the beauty by bib_ibi. Due to the heat generated by the wire, for the $j$-th wire, if both the uju_juj-th bulb and the vjv_jvj-th bulb it connects are lit, an additional cjc_jcj units of power will be consumed. Since lit bulbs also generate heat, for safety reasons, each lit bulb must be directly connected by a wire to at least one unlit bulb.

There is a power meter with a range of $m$, which shows the total power consumption in modulo $m$. There are $q$ queries, each providing $r$ and $k$, and you need to find the maximum beauty of the Christmas tree when only lighting up bulbs in the subtree rooted at the $r$-th bulb, keeping bulbs outside the subtree unlit, and the power meter shows $k$, as well as the number of ways to light up the bulbs that can achieve the maximum beauty.

Two ways to light up the bulbs are considered different if and only if there exists at least one bulb that is lit in one way but not in the other. Since the number of ways may be large, you just need to output it modulo (10⁹+7). If there is no feasible way, the maximum beauty is considered to be $-1$, and the number of ways is $0$.

The first line contains three integers $n$, $m$ and $q$ ($1\le n\le 100$, 1<=m<=3*10⁴,1<=q<=10⁵), indicating the number of bulbs on the Christmas tree, the range of the power meter, and the number of queries.
Then $n$ lines follow, the $i$-th of which contains two integers aia_iai and bib_ibi (1<=a_i,b_i<=10⁶), indicating that lighting up the $i$-th bulb consumes aia_iai units of power and increases the beauty by bib_ibi.
Then $(n-1)$ lines follow, the $j$-th of which contains three integers uju_juj, vjv_jvj and cjc_jcj (1≤ui,vj≤n1 \leq u_i, v_j \leq n1≤ui,vj≤n, 1<=c_j<=10⁶), indicating that the $j$-th wire connects the uju_juj-th bulb and the vjv_jvj-th bulb, and if these bulbs are both lit, an additional cjc_jcj units of power will be consumed. It is guaranteed that the input wires connect all bulbs forming a tree.
Then $q$ lines follow, each of which contains two integers $r$ and $k$ (1≤r≤n1 \leq r \leq n1≤r≤n, 0≤k<m0 \leq k < m0≤k<m), indicating a query.

In the second sample case, a single bulb cannot be lit.