베시가 또 농부 존의 집으로 몰래 잠입했습니다! 베시는 부엌에서 오렌지 더미와 레몬 더미를 발견했습니다.

두 과일은 사실상 무한개로 채워져 있으며, 베시는 배가 터질 때까지 최대한 많이 먹으려고 합니다.

베시의 최대 포만감은 T입니다. 오렌지를 하나 먹으면 포만감이 A만큼 증가하고, 레몬을 하나 먹으면 포만감이 B만큼 증가합니다.

추가로, 베시는 원한다면 탐색 도중 딱 한 번 물을 마실 수 있습니다. 물을 마시면 현재 베시의 포만감은 즉시 절반으로 줄어듭니다. (절반으로 나눈 뒤 소수점 이하는 버립니다, 즉 내림 처리)

베시의 포만감이 최대치인 T를 넘지 않으면서 달성할 수 있는 "최대 포만감"이 얼마인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 개의 정수 T, A, B가 공백을 사이에 두고 주어진다.
(1 ≤ T ≤ 5,000,000, 1 ≤ A, B ≤ T)

출력

베시가 달성할 수 있는 최대 포만감을 나타내는 정수 하나를 출력한다.

출처

USACO 2015 December Contest, Gold

Three integers \(T\), \(A\), \(B\) (\(1 \le T \le 5\,000\,000\), \(1 \le A, B \le T\)).

Print the maximum reachable fullness.

riseoj 작성

출처 Online Judge > GoldOJ