Bottles

https://codeforces.com/problemset/problem/730/J

Nick has n bottles of soda left after his birthday. Each bottle is described by two values: remaining amount of soda ai and bottle volume bi (ai ≤ bi).

Nick has decided to pour all remaining soda into minimal number of bottles, moreover he has to do it as soon as possible. Nick spends x seconds to pour x units of soda from one bottle to another.

Nick asks you to help him to determine k — the minimal number of bottles to store all remaining soda and t — the minimal time to pour soda into k bottles. A bottle can't store more soda than its volume. All remaining soda should be saved.

Input

The first line contains positive integer n (1 ≤ n ≤ 100) — the number of bottles.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 100), where aiis the amount of soda remaining in the i-th bottle.

The third line contains n positive integers b1, b2, ..., bn (1 ≤ bi ≤ 100), where bi is the volume of the i-th bottle.

It is guaranteed that ai ≤ bi for any i.

Output

The only line should contain two integers k and t, where k is the minimal number of bottles that can store all the soda and t is the minimal time to pour the soda into k bottles.

Examples

Input

4
3 3 4 3
4 7 6 5

Output

2 6

Input

2
1 1
100 100

Output

1 1

Input

5
10 30 5 6 24
10 41 7 8 24

Output

3 11

Note

In the first example Nick can pour soda from the first bottle to the second bottle. It will take 3 seconds. After it the second bottle will contain 3 + 3 = 6 units of soda. Then he can pour soda from the fourth bottle to the second bottle and to the third bottle: one unit to the second and two units to the third. It will take 1 + 2 = 3 seconds. So, all the soda will be in two bottles and he will spend 3 + 3 = 6 seconds to do it.

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG

using namespace std;
typedef long long ll;
const int N=100+10;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m;
struct node {
    int a,b;
    bool operator < (const node & S)const{
        if(b!=S.b)
            return b>S.b;
        else
            return a>S.a;
    }
}e[N];
int dp[N][N*N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d",&n);
    int sum=0;
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++){
        scanf("%d",&e[i].a);
        sum+=e[i].a;
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&e[i].b);
    sort(e+1,e+n+1);
    int tmp=0;
    int cnt=0,ans=0;
    for(int i=1;i<=n;i++){
        tmp+=e[i].b;
        if(tmp>=sum){
            cnt=i;
            break;
        }

    }
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=sum;j>=e[i].a;j--){
            for(int k=i;k>=1;k--){
                if(dp[k-1][j-e[i].a]!=-1)
                    dp[k][j]=max(dp[k][j],dp[k-1][j-e[i].a]+e[i].b);
            }
        }
    }

    for(int i=sum;i>=1;i--){
        if(dp[cnt][i]>=sum){
            ans=sum-i;
            break;
        }
    }
    cout << cnt <<" "<< ans << endl;
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二