Stations
The management of the Very Large Railway (VLR) is introducing a new fare system. The VLR operates along a line with N stations arranged sequentially. The plan is to divide these stations into M contiguous zones, where each zone contains at least one station. The fare for traveling between station i and station k is determined by the formula 1 + |z_i − z_k|, where z_i and z_k are the zone numbers of stations i and k, respectively.
The number of passengers traveling daily from each station to every other station is known. Your task is to write a program that calculates the maximum possible daily revenue under this new fare system by optimally dividing the stations into zones.
Input
The input consists of N lines. The first line contains two integers, N and M (1 ≤ M ≤ N ≤ 1000). The second line contains a single number, representing the number of passengers traveling from station 1 to station 2. The third line contains two numbers, indicating the number of passengers traveling from station 1 to station 3 and from station 2 to station 3, respectively. This pattern continues, with the N-th line containing N−1 numbers, where the i-th number specifies the number of passengers traveling from station i to station N. The passenger numbers are given for both directions of travel between each pair of stations. All numbers are non-negative integers and do not exceed 10,000.
Output
The output should be a single integer, representing the maximum daily revenue that can be achieved with the optimal division of stations into zones.