Pop-It

Interview

Time limit1sMemory limit1024 MB

Summary

Given an h by w grid of 0s and 1s, find the fewest cells to flip so that every cell has the same value.

Level: Easy2 of 10
Topics: String, Implementation
Solved: No attempts yet

Problem

Pop-it, from the English phrase pop it, is a button toy that became popular among children and teenagers in spring 2021. It is made of rubber or silicone, and pressing a dome makes a clicking sound. The domes are called bumps, after the bubble wrap that makes a similar popping sound when pressed. (Wikipedia)

In this problem, a pop-it is a rectangle of height $h$ and width $w$ . Each unit cell holds one bump. Every bump is either pushed out or pushed in. We mark pushed out as 0 and pushed in as 1. Flipping a bump changes its state to the opposite.

Dasha wants to restore the pop-it to the way it was sold, where all bumps are in the same state. What is the minimum number of bumps Dasha must flip?

Input

The first line contains two integers $h$ and $w$ , the height and width of the pop-it ( $1 \le h, w \le 100$ ). Each of the next $h$ lines contains $w$ characters, each 0 or 1, with no spaces. These lines describe the state of the bumps.

Output

Print one integer, the minimum number of bumps that must be flipped so that all bumps are in the same state.

Examples2

Example 1
Input
```
2 3
010
001
```
Expected output
```
2
```
Example 2
Input
```
5 4
1111
1010
1101
1010
0111
```
Expected output
```
6
```