Description

Now we need to distribute m sequentially ordered books to k people for copying (transcribing). Each person copies at the same speed, and no book can be assigned to two or more people. The books assigned to each person must be consecutive. For example, the first, third, and fourth books cannot be assigned to the same person.

Please design a distribution scheme that minimizes the total copying time. The copying time is determined by the person who has to copy the most pages.

Input Format

The first line contains two integers, m and k (k ≤ m ≤ 500).
The second line contains m integers, where the i-th integer represents the number of pages in the i-th book.

Output Format

Output k lines, each containing two integers. The i-th line indicates the starting and ending book numbers assigned to the i-th person. The starting numbers in the k lines should be in ascending order. If there are multiple solutions, prioritize the one where the earlier people copy as few books as possible.

Example

Input:

9 3  
1 2 3 4 5 6 7 8 9  

Output:

1 5  
6 7  
8 9  

Explanation:
The first person copies books 1 to 5 (total 15 pages), the second copies books 6 to 7 (total 13 pages), and the third copies books 8 to 9 (total 17 pages). The maximum copying time is 17.

Constraints

• 1 ≤ k ≤ m ≤ 500
• The number of pages in each book is a positive integer.

Approach

1. Binary Search for Minimum Maximum Pages:

   • Use binary search to determine the minimum possible maximum pages any single person has to copy. The search range is between the maximum page count of a single book (lower bound) and the sum of all pages (upper bound).

2. Greedy Assignment:

   • Once the minimum maximum pages (let’s call it max_pages) is found, distribute the books such that no person exceeds max_pages. Start assigning from the last book and move backward to ensure the earlier people get fewer books when possible.

Solution Code

m, k = map(int, input().split())
pages = list(map(int, input().split())
if m == 0:
    for _ in range(k):
        print(0, 0)
    exit()

low = max(pages)
high = sum(pages)
result_max = high

# Binary search to find the minimal maximum pages
while low <= high:
    mid = (low + high) // 2
    current_sum = 0
    required_people = 1
    for page in pages:
        if current_sum + page > mid:
            required_people += 1
            current_sum = page
        else:
            current_sum += page
    if required_people <= k:
        result_max = mid
        high = mid - 1
    else:
        low = mid + 1

# Now distribute the books with result_max
result = []
current_sum = 0
books_assigned = 0
# We need to assign from the end to start to ensure earlier people have fewer books
# So first, we'll collect the segments in reverse order
segments = []
last = m - 1
remaining_people = k
# Iterate from the end to the start
for i in range(m - 1, -1, -1):
    if remaining_people == 0:
        break
    current_sum += pages[i]
    if current_sum > result_max or i < remaining_people - 1:
        segments.append((i + 1, last))
        last = i
        current_sum = pages[i]
        remaining_people -= 1
segments.append((0, last))
segments.reverse()

for seg in segments:
    print(seg[0] + 1, seg[1] + 1)

Explanation

1. Binary Search Setup:

   • The binary search is set between the largest single book page count (low) and the total sum of all pages (high). This helps efficiently narrow down the minimal maximum pages any person must copy.

2. Checking Feasibility:

   • For each midpoint (mid) in the binary search, the algorithm checks how many people are needed if no one copies more than mid pages. If the required people are within the allowed k, it tries a smaller mid; otherwise, it increases mid.

3. Book Distribution:

   • After determining the minimal max_pages, the books are distributed starting from the end. This ensures that earlier segments (people) get as few books as possible while staying under max_pages. The segments are collected in reverse order and then reversed for the final output.

This approach efficiently minimizes the maximum copying time while ensuring the distribution adheres to the constraints and prioritizes earlier people having fewer books.

9 3			
1 2 3 4 5 6 7 8 9

1 5
6 7
8 9