#P50128. 「LibreOJ Round #8」Moejy0viiiiiv's Red Envelopes
「LibreOJ Round #8」Moejy0viiiiiv's Red Envelopes
Description
Moejy0viiiiiv is collecting red envelopes on a rectangular plane. She starts at . Every day at noon, she walks from to with probability , and to with probability , and stops immediately with probability (once she stops, she will never move again). Besides, she also stops after walking for days.
With a given constant integer , there’s a red envelope at each . There’re also barriers at (barriers never coincide with red envelopes). If she walks to a barrier, she will stop immediately.
Moejy0viiiiiv will collect each red envelope she passes by (including ). What’s the expected number of red envelopes Moejy0viiiiiv collects after days? Output the answer . Notice that .
Input Format
The first line contains two positive integers .
The second line contains four positive integers .
The following lines each contains two integers, the -th line contains .
Output Format
Output contains one integer, the expected number of red envelopes .
Sample 1
1 1
2 2 5 1
1 0
2
There’re three red envelopes satisfies , . As there’s a barrier at , the red envelope at is unreachable. The probability of getting the other two red envelopes are both .
doesn’t need to be .
1 2
2 2 5 0
6
Constraints
For all test cases, , .
Detailed constraints are as follows (blank grids denote the same constraints as mentioned above):
Subtask # | Score (percentage) | ||||
---|---|---|---|---|---|
- | |||||
- | |||||
- | |||||
- |