use std::collections::hash_set::Iter;
use std::rc::Rc;
use std::ops::DivAssign;
use std::ops::MulAssign;
use std::ops::SubAssign;
use std::collections::BinaryHeap;
use std::str::FromStr;
use std::collections::HashSet;
use std::collections::BTreeMap;
use std::fmt::Display;
use std::ops::Neg;
use std::ops::Div;
use std::ops::Mul;
use std::ops::Add;
use std::ops::{AddAssign, Sub};
use std::cmp::max;
use std::collections::VecDeque;
use std::cmp::min;
use std::collections::{HashMap, BTreeSet};
use std::cmp::Ordering;
use std::fmt::Debug;

fn read_line() -> String {
    let mut buffer = String::new();
    std::io::stdin().read_line(&mut buffer).expect("No Line");
    buffer.trim().to_owned()
}
fn read_lines<T: std::str::FromStr>(count: usize) -> Vec<T> {
    let mut buffer = String::new();
    let mut vec = Vec::with_capacity(count);
    for _ in 0 .. count {
        std::io::stdin().read_line(&mut buffer).expect("No Line");
        vec.push(buffer.trim().parse().ok().expect("Can't Parse"));
        buffer.clear();
    }
    vec
}
fn read_tabulate<R, T: Fn(&str)->R> (count: usize, transformer: T) -> Vec<R> {
    let mut buffer = String::new();
    let mut vec = Vec::with_capacity(count);
    for _ in 0 .. count {
        std::io::stdin().read_line(&mut buffer).expect("No Line");
        vec.push(transformer(buffer.trim()));
        buffer.clear();
    }
    vec
}
fn read_value<T: std::str::FromStr>() -> T {
    read_line().trim().parse().ok().unwrap()
}
fn read_values<T: std::str::FromStr>() -> Vec<T> {
    read_line().trim().split_whitespace().map(|x| x.parse().ok().expect("Can't Parse")).collect::<Vec<T>>()
}
macro_rules! freeze {
    ($($id:ident), *) => {
        $(let $id = $id;)*
    };
}
macro_rules! read_map {
    ($ident: ident: [$block: block; $size: expr]) => {
        let $ident = (0 .. $size).into_iter().map(|_| $block).collect::<Vec<_>>();
    };
    (mut $ident: ident: [$block: block; $size: expr]) => {
        let mut $ident = (0 .. $size).into_iter().map(|_| $block).collect::<Vec<_>>();
    };
}
macro_rules! read {
    (mut $ident: ident: String) => {
        let mut $ident = read_value::<String>();
    };
    ($ident: ident: String) => {
        let $ident = read_value::<String>();
    };
    (mut $ident: ident: [$ty:ty]) => {
        let mut $ident = read_values::<$ty>();
    };
    ($ident: ident: [$ty:ty]) => {
        let $ident = read_values::<$ty>();
    };
    (mut $ident: ident: [[$ty:ty]; $size: expr]) => {
        let mut $ident = (0 .. $size).into_iter().map(|_| read_values::<$ty>()).collect::<Vec<_>>();
    };
    ($ident: ident: [[$ty:ty]; $size: expr]) => {
        let $ident = (0 .. $size).into_iter().map(|_| read_values::<$ty>()).collect::<Vec<_>>();
    };
    (mut $ident: ident: [$ty:ty; $size:expr]) => {
        let mut $ident = read_lines::<$ty>($size);
    };
    ($ident: ident: [$ty:ty; $size:expr]) => {
        let $ident = read_lines::<$ty>($size);
    };
    ($ident: ident: [$block: block; $size: expr]) => {
        let $ident = (0 .. $size).into_iter().map(|_| $block).collect::<Vec<_>>();
    };
    (mut $ident: ident: [$block: block; $size: expr]) => {
        let mut $ident = (0 .. $size).into_iter().map(|_| $block).collect::<Vec<_>>();
    };
    ($($token: tt)*) => {
        let mut iter = read_values::<String>().into_iter();
        read_from_iter!(iter; $($token)*);
    };
}
macro_rules! read_from_iter {
    ($iter:expr; mut $ident:ident:$ty:ty, $($rest:tt)*) => {
        let mut $ident = $iter.next().unwrap().parse::<$ty>().expect("Can't Parse");
        read_from_iter!($iter; $($rest)*);
    };
    ($iter:expr; $ident:ident:$ty:ty, $($rest:tt)*) => {
        let $ident = $iter.next().unwrap().parse::<$ty>().expect("Can't Parse");
        read_from_iter!($iter; $($rest)*);
    };
    ($iter:expr; mut $ident:ident:$ty:ty) => {
        let mut $ident = $iter.next().unwrap().parse::<$ty>().expect("Can't Parse");
    };
    ($iter:expr; $ident:ident:$ty:ty) => {
        let $ident = $iter.next().unwrap().parse::<$ty>().expect("Can't Parse");
    };
    ($iter: expr; ) => {};
}
struct KeyValue<K, V> {
    key: K,
    value: V
}
impl <K: PartialOrd, V> PartialEq for KeyValue<K, V> {
    fn eq(&self, other: &Self) -> bool {
        self.key.eq(&other.key)
    }
}
impl <K: PartialOrd, V> Eq for KeyValue<K, V> {}
impl <K: PartialOrd, V> PartialOrd for KeyValue<K, V> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.key.partial_cmp(&other.key)
    }
}
impl <K: PartialOrd, V> Ord for KeyValue<K, V> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.key.partial_cmp(&other.key).ok_or("Can't Compare").unwrap()
    }
}
fn move_step(squares: &mut Vec<Vec<HashSet<(usize, usize)>>>, covers: &mut Vec<Vec<HashSet<(usize, usize)>>>) -> (usize, usize) {
    let mut count = 0usize;
    let mut cover = 0usize;
    loop {
        let mut changed = HashSet::new();
        while let Some(&(i, j)) = (0 .. squares.len()).flat_map(|i| (0 .. squares[i].len()).map(move |j| (i, j))).find(|&(i, j)| covers[i][j].len() == 1).map(|(i, j)| covers[i][j].iter().next().unwrap()) {
            count += 1;
            let covered = squares[i][j].iter().cloned().collect::<Vec<_>>();
            //println!("put i: {}, j: {}, put: {:?}", i, j, covered);
            for &(y, x) in &covered {
                for &(yi, xi) in &covers[y][x] {
                    squares[yi][xi].remove(&(y, x));
                    changed.insert((yi, xi));
                }
                covers[y][x].clear();
            }
            squares[i][j].clear();
            cover += covered.len();
        }
        if changed.is_empty() {break;}
        //println!("changed: {:?}", changed);
        for (i, j) in changed {
            if squares[i][j].is_empty() {continue;}
            let overlapped = squares[i][j].iter().map(|&(yi, xi)| &covers[yi][xi]).fold((0 .. squares.len()).flat_map(|y| (0 .. squares[y].len()).map(move |x| (y, x))).collect::<HashSet<_>>(), |a, b| a.intersection(b).cloned().collect::<HashSet<_>>());
            if overlapped.len() > 1 {
                //println!("remove i: {}, j: {}", i, j);
                let covered = squares[i][j].iter().cloned().collect::<Vec<_>>();
                for &(y, x) in &covered {
                    covers[y][x].remove(&(i, j));
                }
                squares[i][j].clear();
            }
        }
    }
    (count, cover)
}
fn search(squares: &mut Vec<Vec<HashSet<(usize, usize)>>>, covers: &mut Vec<Vec<HashSet<(usize, usize)>>>, scratched: usize, current_put: usize, current_min: usize, max_index: (usize, usize)) -> usize {
    if scratched == 0 {return current_put;}
    if current_min <= current_put {return current_min;}
    let (count, cover) = move_step(squares, covers);
    if cover == scratched {return count + current_put;}
    let mut result = current_min;
    for i in 0 .. squares.len() {
        if i < max_index.0 {continue;}
        for j in 0 .. squares[i].len() {
            if i == max_index.0 && j < max_index.1 {continue;}
            if squares[i][j].is_empty() {continue;}
            let mut s = squares.clone();
            let mut c = covers.clone();
            let covered = squares[i][j].iter().cloned().collect::<Vec<_>>();
            //println!("put i: {}, j: {}, put: {:?}", i, j, covered);
            for &(y, x) in &covered {
                for &(yi, xi) in &covers[y][x] {
                    s[yi][xi].remove(&(y, x));
                }
                c[y][x].clear();
            }
            s[i][j].clear();
            let r = search(&mut s, &mut c, scratched - cover - covered.len(), current_put + 1 + count, result, (i, j));
            result = min(r, result);
        }
    }
    result
}
fn solve(state: &Vec<Vec<usize>>) -> usize {
    let mut square_size = state.clone();
    let mut squares = vec![vec![HashSet::<(usize, usize)>::new(); state[0].len()]; state.len()];
    let mut covers = vec![vec![HashSet::<(usize, usize)>::new(); state[0].len()]; state.len()];
    for i in (0 .. state.len() - 1).rev() {
        for j in (0 .. state[i].len() - 1).rev() {
            if square_size[i][j] != 0 {
                square_size[i][j] = min(square_size[i + 1][j + 1], min(square_size[i + 1][j], square_size[i][j + 1])) + 1;
            }
        }
    }
    for i in 0 .. state.len() {
        for j in 0 .. state[i].len() {
            for di in 0 .. square_size[i][j] {
                for dj in 0 .. square_size[i][j] {
                    squares[i][j].insert((i + di, j + dj));
                    covers[i + di][j + dj].insert((i, j));
                }
            }
        }
    }

    for i in 0 .. state.len() {
        for j in 0 .. state[i].len() {
            if squares[i][j].is_empty() {continue;}
            let overlapped = squares[i][j].iter().map(|&(yi, xi)| &covers[yi][xi]).fold((0 .. state.len()).flat_map(|y| (0 .. state[y].len()).map(move |x| (y, x))).collect::<HashSet<_>>(), |a, b| a.intersection(b).cloned().collect::<HashSet<_>>());
            if overlapped.len() > 1 {
                //println!("remove i: {}, j: {}", i, j);
                //println!("remove i: {}, j: {}, overlapped: {:?}", i, j, overlapped);
                let covered = squares[i][j].iter().cloned().collect::<Vec<_>>();
                for &(y, x) in &covered {
                    covers[y][x].remove(&(i, j));
                }
                squares[i][j].clear();
            }
        }
    }
    search(&mut squares, &mut covers, state.iter().map(|line| line.iter().sum::<usize>()).sum::<usize>(), 0, std::usize::MAX, (0, 0))
}

fn main() {
    loop {
        read!(width: usize, height: usize);
        if height == 0 && width == 0 {break; }
        read!(state: [[usize]; height]);
        println!("{}", solve(&state));
    }
}


Measured memory_bytes: 5072