Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Ở 1 con vỉa hè chạy dọc theo bờ sông Hàn tại thành phố Đà Nẵng có một chiếc máy gắp gấu bông siêu to không lồ. Ở trong lồng kính của máy có tổng cộng \(n \times n\) ô vuông, mỗi ô vuông chứa một con gấu bông có giá trị là \(a_{ij}\).

Yêu cầu: Bạn được phép gắp \(k\) con gấu bông \((k < n*n)\). Hãy tìm cách gắp sao cho \(k\) con gấu bông gắp được có giá trị lớn nhất.

Input

  • Dòng đầu ghi hai số nguyên dương \(n\)\(k\) không quá \(350\). Dữ liệu đảm bảo \(k < n*n\).
  • \(n\) dòng tiếp theo, mỗi dòng ghi \(n\) số nguyên dương \(a_{ij}\) không quá \(300\).

Output

  • Ghi ra giá trị lớn nhất có thể đạt được theo yêu cầu đề bài.

Example

Test 1

Input
3 4
1 8 9
5 8 8
10 2 9
Output
36

Bình luận


  • 3
    obamagaming    5:18 p.m. 26 Tháng 5, 2022

    năm mới vui vẻ OwO

    || Hint
    Test
    ||


    • 3
      nguyenthienchinh    6:27 p.m. 25 Tháng 1, 2022

      Năm mới vui vẻ các bạn :))))


      • 1
        NghiaUwU    8:09 a.m. 20 Tháng 1, 2022

        ngày mới dui dẻ UwU