Brick Wall

There is a rectangular brick wall in front of you. The wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in that row from left to right.

You need to draw a vertical line from the top to the bottom of the wall, crossing the fewest bricks as possible. If your line goes through the edge between two bricks, that brick is not considered crossed.

Return the minimum number of bricks the line must cross.

You cannot draw a line along the two vertical edges of the wall, so you must cross at least one layer of bricks.

Examples

Example 1:

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]

Output: 2

Explanation: Drawing a vertical line at position 4 from the left crosses only 2 bricks. Multiple rows have an edge at position 4.

Example 2:

Input: wall = [[1],[1],[1]]

Output: 3

Explanation: Every row is a single brick. Any vertical line must cross all 3 bricks.

Example 3:

Input: wall = [[1,1],[2],[1,1]]

Output: 1

Explanation: Drawing a line at position 1 crosses edges in rows 1 and 3, but must cross the brick in row 2.

Constraints

• 1 <= wall.length <= 10^4
• 1 <= wall[i].length <= 10^4
• 1 <= wall[i][j] <= 2^31 - 1
• The sum of brick widths in each row is the same