## Description

Bessie has broken into Farmer John's house again! She has discovered a pile of lemons and a pile of oranges in the kitchen (effectively an unlimited number of each), and she is determined to eat as much as possible.

Bessie has a maximum fullness of T (1≤T≤5,000,000). Eating an orange increases her fullness by A, and eating a lemon increases her fullness by B (1≤A,B≤T). Additionally, if she wants, Bessie can drink water at most one time, which will instantly decrease her fullness by half (and will round down).

Help Bessie determine the maximum fullness she can achieve!

Bessie的饱胀值一开始是0，且上限是T，每个柠檬派可以提供A点饱胀值，每个橘子派可以提供B点饱胀值。

Bessie可以不断地吃东西，如果她的饱胀值没有超出T的话。同时，Bessie有一次喝水的机会，喝完后，她的饱胀值将减少一半（往下取整）。

## Input

The first (and only) line has three integers T, A, and B.

## Output

A single integer, representing the maximum fullness Bessie can achieve.

8 5 6

8

## Source

```#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair
#define maxn 5000100
#define inf 1000000000
using namespace std;
int a,b,t,ans;
bool f[maxn][2];
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
f[0][0]=true;
F(j,0,1) F(i,0,t) if (f[i][j])
{
if (i+a<=t) f[i+a][j]=true;
if (i+b<=t) f[i+b][j]=true;
if (!j) f[i/2][1]=true;
}
ans=t;
while (!f[ans][0]&&!f[ans][1]) ans--;
printf("%d\n",ans);
}
```