Overview

We plant \(N\) flower seeds one by one in order, but cannot work during rainy periods. The problem asks on which day all seeds will be planted.

Analysis

In this problem, we plant \(N\) seeds at a rate of 1 per day, but cannot work during rainy periods. Therefore, the number of seeds that can be planted by day \(d\) is “the total number of days up to \(d\)” minus “the number of rainy days.”

A naive approach of simulating day by day would yield the answer, but the constraints are extremely large with \(N \leq 10^9\) and \(R_i \leq 10^{18}\), making this impractical (TLE).

Therefore, we apply the following two optimizations: 1. Merge rainy periods: Combine overlapping or adjacent intervals to handle them efficiently. 2. Find the answer using binary search: Narrow down the final date using binary search, and quickly compute the number of seeds that can be planted by that date.

Specifically, the number of seeds that can be planted by day \(d\) is \(d - (\text{number of rainy days})\). The number of rainy days can be computed cumulatively over the merged intervals.

Algorithm

1. Sort the rainy intervals \((L_i, R_i)\) by start day \(L_i\).
2. Merge adjacent or overlapping intervals to obtain mutually disjoint rainy periods.
3. For each interval, compute the “cumulative number of non-rainy days up to that point” and store it in a list.
4. If the total number of non-rainy days is at least \(N\), use binary search to find “the minimum day on which \(N\) seeds can be planted.”
   • For each candidate day, calculate the “number of rainy days” up to that day along the intervals, and evaluate the number of seeds that can be planted.
5. If the number of non-rainy days is insufficient, add the required number of days after the last rainy day to obtain the answer.

Complexity

• Time complexity: \(O(M \log M + M \log D)\)
  (where \(D\) is the maximum value of the search range, roughly \(10^{18}\))
• Space complexity: \(O(M)\)

Note: Sorting the intervals takes \(O(M \log M)\), and in the binary search phase, an \(O(M)\) computation is repeated \(\log D\) times.

Implementation Notes

• Use sys.stdin.read for fast input reading.
• Merging intervals only needs to be done once after sorting.
• During binary search, the number of rainy days up to day mid must be counted accurately.
• Since the constraints are large, be careful with int types and the range of binary search.

## Source Code

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    if M == 0:
        print(N)
        return
    
    intervals = []
    idx = 2
    for _ in range(M):
        L = int(data[idx])
        R = int(data[idx+1])
        intervals.append((L, R))
        idx += 2
    
    # 区間を開始日でソート
    intervals.sort()
    
    # 区間のマージ
    merged = []
    for L, R in intervals:
        if not merged or merged[-1][1] < L - 1:
            merged.append((L, R))
        else:
            merged[-1] = (merged[-1][0], max(merged[-1][1], R))
    
    # 各区間までの非雨日数を計算
    total_rainy_days = 0
    prev_end = 0
    non_rainy_count = 0
    cumulative_non_rainy = []  # (day, non_rainy_count)
    
    for L, R in merged:
        # 前の区間の次の日から現在の区間の前日までの日数
        gap = L - 1 - prev_end
        if gap > 0:
            non_rainy_count += gap
        total_rainy_days += R - L + 1
        cumulative_non_rainy.append((R, non_rainy_count))
        prev_end = R
    
    # N個の種を植える必要がある
    if non_rainy_count >= N:
        # 二分探索でN個目に種を植える日を探す
        left = 1
        right = merged[-1][1]
        while left < right:
            mid = (left + right) // 2
            # mid日までに植えられる種の数を計算
            count = mid
            # mid日までの雨の日数を引く
            rainy = 0
            for L, R in merged:
                if R < mid:
                    rainy += R - L + 1
                elif L <= mid:
                    rainy += mid - L + 1
                else:
                    break
            count -= rainy
            if count >= N:
                right = mid
            else:
                left = mid + 1
        print(left)
    else:
        # 最後の区間の後ろにまだ日が必要
        remaining = N - non_rainy_count
        last_day = merged[-1][1]
        result = last_day + remaining
        print(result)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.