[C++知识库]C. Table Decorations

You have?r?red,?g?green and?b?blue balloons. To decorate a single table for the banquet you need exactly three balloons. Three balloons attached to some table shouldn't have the same color. What maximum number?t?of tables can be decorated if we know number of balloons of each color?

Your task is to write a program that for given values?r,?g?and?b?will find the maximum number?t?of tables, that can be decorated in the required manner.

Input

The single line contains three integers?r,?g?and?b?(0?≤?r,?g,?b?≤?2·109) — the number of red, green and blue baloons respectively. The numbers are separated by exactly one space.

Output

Print a single integer?t?— the maximum number of tables that can be decorated in the required manner.

Examples

Input

5 4 3

Output

4

Input

1 1 1

Output

1

Input

2 3 3

Output

2

Note

In the first sample you can decorate the tables with the following balloon sets: "rgg", "gbb", "brr", "rrg", where "r", "g" and "b" represent the red, green and blue balls, respectively.

题意：给r个红色气球，g个绿色气球，b个蓝色气球，把它们放在桌子上，要求不能三个气球颜色都一样，求最多能组成多少桌子

题解：一开始想的是构造，但越想越感觉复杂，后来发现用二分就能做了，如果要满足当前的桌子数，必须满足任意两个颜色相加都大于等于桌子数，才能分配。

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cstring>
#include<vector>
#include<set>
#include<cmath>
#include<cstring>
#include<cstdlib>
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define PII pair<int,int>
#define ll long long
#define ull unsigned long long
#define PLL pair<long long,long long>
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scl(a) scanf("%lld",&a)
#define rep(i,n) for(int i = 0; (i)<(n); i++)
#define rep1(i,n) for(int i = 1; (i)<=(n); i++)
#define pb(a) push_back(a)
#define mst(a,b) memset(a, b, sizeof a)
using namespace std;
ll a,b,c;
bool check(ll mid)       //判断三个颜色能不能都符合当前桌子最少需求量
{
    if(a+b<mid) return false;
    if(a+c<mid) return false;
    if(b+c<mid) return false;
    return true;
}
void solve()
{
    cin>>a>>b>>c;
    ll l=0,r=(a+b+c)/3;
    while(l<r)
    {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<r;
}

int main()
{
    int t=1;
   // scd(t);
    while(t--) solve();
    return 0;
}

后面发现也能用贪心做，如果数量少的两个颜色气球的两倍少于数量最多的气球，那答案数就由两个数量少的决定，否则答案就是三个人的数量和除以三

代码如下

void solve()
{
    cin>>a>>b>>c;
    if(a>b) swap(a,b);
    if(b>c) swap(b,c);
    if(a>b) swap(a,b);
    if(a+b<c/2) cout<<a+b<<endl;
    else cout<<(a+b+c)/3<<endl;
}