Alice gives Bob a board composed of wooden squares and asks him to find the minimum cost of breaking the board back down into its individual squares. To break the board down, Bob must make cuts along its horizontal and vertical lines.

To reduce the board to squares, Bob makes horizontal and vertical cuts across the entire board. Each cut has a given cost, or for each cut along a row or column across one board, so the cost of a cut must be multiplied by the number of segments it crosses. The cost of cutting the whole board down into squares is the sum of the costs of each successive cut.

Can you help Bob find the minimum cost? The number may be large, so print the value modulo .

For example, you start with a board. There are two cuts to be made at a cost of for the horizontal and for the vertical. Your first cut is across piece, the whole board. You choose to make the horizontal cut between rows and for a cost of . The second cuts are vertical through the two smaller boards created in step between columns and . Their cost is . The total cost is and .

Function Description

Complete the boardCutting function in the editor below. It should return an integer.

boardCutting has the following parameter(s):

• cost_x: an array of integers, the costs of vertical cuts
• cost_y: an array of integers, the costs of horizontal cuts