#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 i^{th} 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 P_{ij} (0 ≤ P_{ij} ≤ 1) to four decimal places. The (i+1)^{th} line contains i numbers, with the j^{th} number indicating the probability of the disk falling to the **left** of the j^{th} stud of that row when it falls on that stud.

The last line contains a row of N+1 space-separated integers S_{i} (0 ≤ S_{i} ≤ 1000000) with the i^{th} integer indicating the number of points gained when the disk falls into the i^{th} 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%): P_{ij} = 0.5 for all P_{ij}.

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 10 | 10 | 1s | 32MB | Minimum |

2 | 20 | 12 | 1s | 32MB | Minimum |

3 | 70 | 12 | 1s | 32MB | Minimum |

4 | 0 | 1 | 1s | 32MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o diskdrop -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512