Hard Rock

Ilya is a frontman of the most famous rock band on Earth. Band decided to make the most awesome music video ever for their new single. In that music video Ilya will go through Manhattan standing on the top of a huge truck and playing amazing guitar solos. And during this show residents of the island will join in singing and shaking their heads. However, there is a problem. People on some streets hate rock.

Recall that Manhattan consists of n vertical and m horizontal streets which form the grid of ( n − 1)×( m − 1) squares. Band’s producer conducted a research and realized two things. First, band’s popularity is constant on each street. Second, a popularity can be denoted as an integer from 1 to 10 ⁹. For example, if rockers go along the street with popularity equal to 10 ⁹ then people will greet them with a hail of applause, fireworks, laser show and boxes with... let it be an orange juice. On the other hand, if rockers go along the street with popularity equal to 1 then people will throw rotten tomatoes and eggs to the musicians. And this will not help to make the most awesome music video!

So, a route goes from the upper left corner to the bottom right corner. Let us define the route coolness as the minimal popularity over all streets in which rockers passed non-zero distance. As you have probably guessed, the musicians want to find the route with the maximal coolness. If you help them then Ilya will even give you his autograph!

Input

In the first line there are integers n and m (2 ≤ n, m ≤ 10 ⁵), separated by space. These are the numbers of vertical and horizontal streets, respectively.

In the following n lines there are popularity values (one value on each line) on vertical streets in the order from left to right.

In the following m lines there are popularity values (one value on each line) on horizontal streets in the order from top to bottom.

It is guaranteed that all popularity values are integers from 1 to 10 ⁹.

Output

Output a single integer which is a maximal possible route coolness.

Example

input	output
2 3 4 8 2 7 3	4
4 3 12 4 12 3 21 5 16	12

解题思路：

题意：求从左上角刀右下角所经过街道的最小的权值，直接分成4种情况：不好描述，直接看代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int m,n,i,a[100009],b[100009];
    cin>>m>>n;
    int maxn = -111111,maxm = -111111;
    for(i=0;i<m;i++){
        cin>>a[i];
        if(a[i]>maxn&&i!=m-1&&i!=0)
            maxn = a[i];
    }
    for(i=0;i<n;i++){
        cin>>b[i];
        if(b[i]>maxm&&i!=n-1&&i!=0)  maxm = b[i];
    }
    int min1 = min(b[0],a[m-1]);
    int min2 = min(a[0],b[n-1]);
    int min3 = min(a[0],min(maxm,a[m-1]));
    int min4 = min(b[0],min(maxn,b[n-1]));
    //cout<<min1<<min2<<min3<<min4<<endl;
    int ans = max(max(min1,min2),max(min3,min4));
    cout<<ans<<endl;
    return 0;
}