Problem Description
The disk drop game is a once-popular arcade game where you drop a disk into a flat, inclined board covered with studs arranged in a regular fashion. Whenever the disk fall on a stud, there's a chance of it falling to the left or right of it. You can assume that this probability does not depend on the direction from which the disk fell. When the disk reaches the bottom of the board, depending on its position, it would fall into a hole indicating the number of points gained.
Your board is a special board where the studs are arranged in a pyramid. In other words, the studs are arranged in N rows with i studs on the ith row.
You have analysed the path of millions of disks through this board and calculated the probability of each disk falling to the left or right of each stud. Find the expected number of points you would gain by dropping a disk at the apex of the pyramid of studs.
Input
The first line contains a single integer N (1 ≤ N ≤ 1000).
The next N lines each contain a row of space-separated numbers Pij (0 ≤ Pij ≤ 1) to four decimal places. The (i+1)th line contains i numbers, with the jth number indicating the probability of the disk falling to the left of the jth stud of that row when it falls on that stud.
The last line contains a row of N+1 space-separated integers Si (0 ≤ Si ≤ 1000000) with the ith integer indicating the number of points gained when the disk falls into the ith hole.
Output
Output a single integer indicating the expected number of points gained if you dropped a disk at the apex of the stud pyramid, rounded down to the nearest integer.
Subtasks
Subtask 1 (10%): Pij = 0.5 for all Pij.
Subtask 2 (20%): 1 ≤ N ≤ 20.
Subtask 3 (70%): No restrictions.
Subtask 4 (0%): Sample test case
Sample Input
2
0.3000
0.4000 0.2000
30 10 20
Sample Output
18
Sample Output Explanation
0.3*0.4*30 + 0.3*0.6*10 + 0.7*0.2*10 + 0.7*0.8*20 = 18