1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
use std::io;
use std::io::Write;
use std::str;
use std::cmp::{max,min};

/// https://github.com/EbTech/rust-algorithms/blob/master/src/scanner.rs
pub struct Scanner<R> {
    reader: R,
    buffer: Vec<String>,
}

impl<R: io::BufRead> Scanner<R> {
    pub fn new(reader: R) -> Self {
        Self {
            reader,
            buffer: vec![],
        }
    }

    pub fn token<T: str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok().expect("Failed parse");
            }
            let mut input = String::new();
            self.reader.read_line(&mut input).expect("Failed read");
            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }
}

fn main() {
    let mut scan = Scanner::new(io::stdin().lock());

    let n = scan.token::<i32>();
    let m = scan.token::<i32>();
    let k = scan.token::<i32>();
    
    let (inc, dec) = 
        (0..n).map(|_| (0..m).map(|_| scan.token()).collect::<Vec<i64>>())
        .partition::<Vec<_>, _>(|row| row.is_sorted());

    let mut dec = dec.into_iter().flatten().collect::<Vec<_>>();
    dec.sort_by_key(|x| -x);
    let dec = dec.into_iter().scan(0, |state, x| {
        *state += x;
        Some(*state)
    }).collect::<Vec<_>>();

    // eprintln!("inc = {inc:?}");

    let mut inc = inc.into_iter().map(|c| c.into_iter().scan(0, |state, x| {
        *state += x;
        Some(*state)
    }).collect::<Vec<_>>()).collect::<Vec<_>>();
    inc.sort_by_key(|x| -x.last().unwrap());
    let inc_cols_sums = inc.iter().scan(0,|state, x| {
        *state += x.last().unwrap();
        Some(*state)}
    ).collect::<Vec<_>>();

    // eprintln!("{dec:?} {inc:?} {inc_cols_sums:?}");

    let mut stacks = (0..m as usize).map(|j| {
        let mut s = vec![];
        for i in (0..inc.len()).rev() {
            if inc[i][j] > s.last().unwrap_or(&(-1i64, 0)).0 {
                s.push((inc[i][j], i));
            }
        }
        s
    }).collect::<Vec<_>>();

    // eprintln!("{stacks:?}");

    let mut res = 0;
    let mut first_iter = true;
    for used_from_dec in (0..min(k+1, dec.len() as i32+1)).rev() {
        let s_dec = if used_from_dec == 0 {
            0
        } else {
            dec[used_from_dec as usize-1]
        };

        let used_cols_from_inc = (k-used_from_dec)/m;
        let s_cols_inc = if used_cols_from_inc == 0 || inc_cols_sums.len() == 0 {
            0
        } else {
            inc_cols_sums[min(inc_cols_sums.len()-1, used_cols_from_inc as usize-1)]
        };

        let rem = (k-used_from_dec)%m;

        if first_iter || rem == 0 {
            for j in 0..m as usize {
                while stacks[j].last().map(|x| x.1+1 <= used_cols_from_inc as usize) == Some(true) {
                    stacks[j].pop().unwrap();
                }
            }
        }

        let s_rem = if rem == 0 || stacks.len() == 0 {
            0
        } else {
            stacks[rem as usize-1].last().unwrap_or(&(0,0)).0
        };
        // eprintln!("cand {}", s_dec + s_cols_inc + s_rem);
        res = max(res, s_dec + s_cols_inc + s_rem);
        first_iter = false;
    }

    let mut out = io::BufWriter::new(io::stdout().lock());
    writeln!(out, "{res}").unwrap();
}