Treasure Hunt Key

Legend has it that on the top floor of a distant treasure tower lies an irresistible treasure. After many hardships, Xiao Ming finally finds this fabled tower. At the entrance, a wooden board displays the words "Treasure Hunt Instructions." The instructions read as follows:

The tower has \(N+1\) floors. The top floor contains a single room with the treasure. Every other floor (i.e. the lower \(N\) floors) contains \(M\) rooms arranged in a circle and numbered \(0, 1, \ldots, M-1\) in anticlockwise order. Some of these rooms have a staircase leading to the next floor. Note that the staircase layout may differ from one floor to another.

Each room has a sign board displaying an integer \(x\). This number instructs you to choose the \(x\)th room that has a staircase when searching in anticlockwise order starting from the current room. Here, if the current room itself has a staircase, it is considered as the first candidate. In other words, suppose the sign board shows \(x\) and you are in room \(r\); then, scanning the rooms in anticlockwise order beginning with room \(r\), the \(x\)th room you encounter that has a staircase is chosen, and you ascend to the next floor arriving at the room with the same index.

The final note on the board (written in large red font) states:

"Treasure Hunt Notice: The key to open the treasure chest is the sum of the numbers on the sign boards of the first room you enter on each floor (that is, the room where you take the staircase)."

Your task is to help Xiao Ming calculate this key.

inputFormat

The first line of input contains two integers \(N\) and \(M\) --- the number of floors (excluding the top treasure floor) and the number of rooms on each floor, respectively.

For each of the following \(N\) floors (from bottom to top), there are two lines:

• The first line contains \(M\) integers, representing the sign board numbers in rooms \(0\) to \(M-1\).
• The second line contains \(M\) integers (each either 0 or 1), where 1 indicates that the corresponding room has a staircase and 0 indicates it does not.

Assume that when you start on the first floor (floor 0), you enter room 0.

outputFormat

Output a single integer --- the sum of the sign board numbers of the rooms from which you take the staircase on each floor.

sample

2 4
2 1 3 2
1 0 1 0
1 2 1 3
0 1 1 1

3