SP1748 SEQPAR2 - Sequence Partitioning II

Given a sequence of _N_ ordered pairs of positive integers (_A $ _{i} $_ , _B $ _{i} $_ ), you have to partition it into several contiguous parts. Let _p_ be the number of these parts, whose boundaries are (_l_ $ _{1} $ , _r_ $ _{1} $ ), (_l_ $ _{2} $ , _r_ $ _{2} $ ), ... ,(_l $ _{p} $_ , _r $ _{p} $_ ), which satisfy _l $ _{i} $_ = _r $ _{i-} $_ $ _{1} $ + 1, _l $ _{i} $_ _A $ _{q} $_ . 2. Let _M $ _{i} $_ be the maximum _A_-component of elements in the _i_th part, say _M $ _{i} $_ = max {_A $ _{li} $_ , _A $ _{li+} $_ $ _{1} $ , ..., _A $ _{ri} $_ }, 1

The input contains exactly one test case. The first line of input contains two positive integers N (N

Output the minimum target value.