A. Greed CodeForces - 892A_综合

http://codeforces.com/problemset/problem/892/A

Jafar has n cans of cola. Each can is described by two integers: remaining volume of cola ai and can's capacity bi (ai ?≤? bi).

Jafar has decided to pour all remaining cola into just 2 cans, determine if he can do this or not!

Input

The first line of the input contains one integer n (2?≤?n?≤?100?000) — number of cola cans.

The second line contains n space-separated integers a1,?a2,?...,?an (0?≤?ai?≤?10^9) — volume of remaining cola in cans.

The third line contains n space-separated integers that b1,?b2,?...,?bn (ai?≤?bi?≤?10^9) — capacities of the cans.

Output

Print "YES" (without quotes) if it is possible to pour all remaining cola in 2 cans. Otherwise print "NO" (without quotes).

You can print each letter in any case (upper or lower).

Examples

Input

2
3 5
3 6

Output

YES

Input

3
6 8 9
6 10 12

Output

NO

Input

5
0 0 5 0 0
1 1 8 10 5

Output

YES

Input

4
4 1 0 3
5 2 2 3

Output

YES

Note

In the first sample, there are already 2 cans, so the answer is "YES".

题意：

其实这个题意是比较简单的，要求第一行给出一个整数n表示n罐可乐，第二行是n个数来表示n个罐中剩余的可乐的体积，第三行是n个数来表示这n个罐的容量。然后来判断这些剩余的所有可乐能否全部装到n个罐中任选的两个罐中。

思路：

计算出所有剩余可乐的体积，然后与n个罐中体积最大的两个罐来比较就可以了。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{long long i,n,x,y,sum=0;long long max1=0,max2=0;  //max1来存放最大的可乐罐的体积，max2来存放第二大的可乐罐体积scanf("%lld",&n);for(i=0;i<n;i++){scanf("%lld",&x);sum+=x;     //sum来存放所有剩余可乐的体积}for(i=0;i<n;i++){scanf("%lld",&y);if(y>=max1){max2=max1;max1=y;}else if(y>max2){max2=y;}}if(sum <= max1+max2)printf("Yes\n");else printf("No\n");return 0;
}