2017-10-25 13:48

Sequence Partitioning

  • bi
  • ai
  • it
  • lines
  • each

Given a sequence of N ordered pairs of positive integers (Ai, Bi), you have to partition it into several contiguous parts. Let p be the number of these parts, whose boundaries are (l1, r1), (l2, r2), ... ,(lp, rp), which satisfy li =ri − 1 + 1, li ≤ ri, l1 = 1, rp = n. The parts themselves also satisfy the following restrictions:
For any two pairs (Ap, Bp), (Aq, Bq), where (Ap, Bp) is belongs to the Tpth part and (Aq, Bq) the Tqth part. If Tp < Tq, then Bp > Aq.
Let Mi be the maximum A-component of elements in the ith part, say
Mi = max{Ali, Ali+1, ..., Ari}, 1 ≤ i ≤ p
it is provided that

where Limit is a given integer.
Let Si be the sum of B-components of elements in the ith part. Now I want to minimize the value
max{Si:1 ≤ i ≤ p}
Could you tell me the minimum?
The input contains exactly one test case. The first line of input contains two positive integers N (N ≤ 50000), Limit (Limit ≤ 231-1). Then follow N lines each contains a positive integers pair (A, B). It's always guaranteed that
max{A1, A2, ..., An} ≤ Limit

Output the minimum target value.
Sample Input
4 6
4 3
3 5
2 5
2 4
Sample Output

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享