#555. 「LibreOJ Round #8」Moejy0viiiiiv's Red Envelopes / 抢红包

题目描述

Moejy0viiiiiv 在平面直角坐标系上抢红包。从 出发，每天中午有 的概率向上走一格，有 的概率向右走一格，有 的概率立即停止行动（之后也不再行动），三种事件两两不会同时发生；Moejy0viiiiiv 在第 天傍晚离开平面直角坐标系（总共至多走 格）。

Moejy0viiiiiv 会抢走所有她经过的红包（包含 ）问最终期望抢到的红包数量，输出这个值 ，注意

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 .

输入格式

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 contains one integer, the expected number of red envelopes .

样例输入1

1 1
2 2 5 1
1 0


样例输出 1

2


样例输入 2

1 2
2 2 5 0


样例输出 2

6


Sample Input 1

1 1
2 2 5 1
1 0


Sample Output 1

2


Sample Explanation 1

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 .

Sample Input 2

1 2
2 2 5 0


Sample Output 2

6


数据范围与提示

-
-
-
-

For all test cases, , .

Detailed constraints and hints are as follows (blank grids denote the same constraints as mentioned above):