01 Grid

Statement

Goal

Tourist is playing a new game called 01 Grid.
You are given an R rows and C columns grid made up of 0 and 1.

We define an operation in two steps:
1) Choose any cell
2) Toggle the value v of this cell (if v = 0 then v becomes 1 and if v = 1 it becomes 0).

You have to process exactly K operations.

Your task is to apply these operations in a way that maximize the sum of the cells in the grid.

Input

Line 1 : Three integers: R (the number of rows), C (the number of columns), K (the number of operations you have to apply)

R next lines : C integers denoting the value of each cell of the grid

Output

Line 1 : One integer, the maximum sum of the cells of the grid we can achieve after applying exactly K operations

Constraints

1 <= R, C <= 1000

0 <= K <= 1 000 000 000

Example

Input

4 10 9
1 0 1 0 1 1 1 0 0 0 
1 1 1 1 0 1 0 1 0 0 
0 0 0 0 0 1 0 1 1 0 
1 1 0 1 1 0 1 0 0 1

Output

Tags

adhoc, Greedy algorithms, Mathematics, Modular calculus

Difficulty

Easy

Test cases

Small grid Test

Input

4 10 9 1 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1

Output

Few operations Validator

Input

2 19 5 1 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1

Output

Column vector Test

Input

530 4 687628513 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 1 1 1 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 1 0 1 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 0 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1

Output

2119

Ones uppon a time Validator

Input

366 10 983294325 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Output

3659

Medium grid Test

Input

501 9 444334873 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 1 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 0

Output

4508

Edge case (: Validator

Input

627 7 0 1 0 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0 1 1 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 1 1 0 1 1 1 0 0 1 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 0

Output

2238

Limit testing 1 Test

Input

848 5 635031905 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0

Output

4239

Limit testing 2 Validator

Input

900 5 1000000000 0 0 0 0 1 1 1 0 1 1 1 1 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 1 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1

Output

4499

Special case Test

Input

3 3 12 0 1 1 1 0 1 1 1 1

Output

I'm lazy Validator

Input

3 3 11 0 1 1 1 0 1 1 1 1

Output

Solution language

Solution

Stub generator input

Comments

17 Comments

java_coffee_cup Unnamed CodinGamer

over 4 years ago

❌ Rejected the contribution. Comment: Too trivial. Too obvious. Too exaggerated labeling as "Modular calculus"

Westicles Unnamed CodinGamer

❌ Rejected the contribution. Comment: Agree with Niako, too much effort doing something trivial

Niako Unnamed CodinGamer

❌ Rejected the contribution. Comment: As selenae mentioned, that's more of an obfuscated trivial task than an actual puzzle. No interest as a classic puzzle IMO.

selenae Unnamed CodinGamer

Too easy. I'm not a fan of obfuscating a simple math problem with a lot of unnecessary noise. In this case, the details of the grid are unnecessary. All that matters is the area of the grid and sum of the 1's plus K.

Vicllo Unnamed CodinGamer

Nice puzzle, really interesting maths going with it. Medium difficulty is I think a good thing. Ready for submission imo

y42nn Unnamed CodinGamer

Thank you for your advice :)

Tutmalo Unnamed CodinGamer

There's an error in stub generator input, the inner for loop looks like "for (int j = 0; j < cell; j++)" instead of "j < C". The explanation for toggling the value does not need to be so specific, first sentence suffices. Not sure this requires Greedy algorithm tag as it is a simple math puzzle, tag might only confuse people. Other than that, in my opinion it looks more like an easy puzzle than medium one.

Hey ! I also consider this as an easy puzzle but I found a lot of medium puzzles easy so... "the inner for loop looks like "for (int j = 0; j < cell; j++)" instead of "j < C"." Thank you for the report :D I added greedy algorithm tag as the solution is to greedly toggle all cells to 1 then use the missing operations to toggle the same cell

UnicornP Unnamed CodinGamer

This is a cool CoC, and most certainly not a medium puzzle in its current form (it's a WIP though so I guess you haven't put the extra stuff in yet). I was expecting there to be something like "maximize the sum for each odd row and minimize the sum for each even row" or some other optimization goal like that. The key missing part right now is that the puzzle has nothing to do with a grid. Right now, the bulk of the answer is simply to sum up the 1's in the entire input and add K to it without bothering to look at what the grid looks like.

Well your answer is totally wrong x)