8498: Equipment Upgrade

Little Q is playing an RPG game. In this game, the weapon can be upgraded. Initially, the weapon is at level $0$, and the upper bound of the level is n. Assume the current level is $i$ ($0\le i<n$), Little Q can pay ci coins to upgrade the weapon, the next level will be $i$with probability pi, and will be i-j($1\le j\le i$) with probability ∑k=1iwkwj.

Though Little Q is very rich, he is still wondering the expected number of coins for him to upgrade the weapon from level $0$ to level n. Please write a program to help him.

The first line contains a single integer T($1\le T\le 300$), the number of test cases. For each test case:

The first line contains a single integer n ($2\le n\le 100,000$), denoting the upper bound of the level.

The ith ($1\le i\le n$) of the following n lines contains two integersPi−1 andci−1 (1≤Pi−1,ci−1≤100), describing the success probability and the cost for level $i-1$. Here pi−1=100Pi−1. It is guaranteed thatP0=100.

The next line contains n-1 integers w1,w2,…,wn−1 (1≤wi≤100).

It is guaranteed that the sum of all n is at most 500,000.

For each test case, output a single line containing an integer, denoting the expected number of coins to level n

More precisely, if the answer is P/Q, you should output the minimum non-negative integer rsuch that $q\cdot r\equiv p(\mathrm{mod}998,244,353)$. You may safely assume that such r always exists in all test cases.

2
2
100 1
50 5
1
3
100 1
70 2
50 3
2 3

12
228170152