A2. Fire tower 3D (hard version)
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
2 2 1 2
1 1
Output
11
Input
1 5 1 10
1 3
Output
53
Input
4 3 6 6
1 1
2 2
3 1
3 3
4 1
4 2
Output
83