#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; template T gcd(T a, T b) { if ( std::abs(a) < std::abs(b) ) std::swap(a,b); if ( b == 0 ) return a; return gcd(b, a%b); } class TwoKindsOfStamp { public: ll roundUp(ll a, ll b) { ll x = ceil((double)a/b); return (x>=0)? x : 0; } void solve(void) { ll A,B,T; cin>>A>>B>>T; // f(n,m) = n*A + m*B >= T // を満たす f(n,m) の最小値をもとめればよい // // A,B < 10^9 なので単純な全探索では間に合わない。 // // m を固定してみる。このとき条件をみたすには n は // n >= (T - m*B)/A // n >= ceil((T-m*B)/A) // を満たす必要がある。 // // よって m を固定したときのとりうる f(n,m) の最小値は // f(n,m) = ceil((T-m*B)/A)*A + m*B // // m > T/B を超えると T-m*B < 0 になってしまうので m <= T/B まで探索すればよい。 // このままだと B が小さいときは T < 10^9 のままなので間に合わない // // そこで m > A のときを考えると // f(n,m) = n*A + (m'-A*k)*B (m = m'-A*k, k >= 1) // = (n-B*k)*A + m'*B (m' < A) // とかけるので m <= A と見なしてよい // // よって探索上限は min(T/B,A) となり // T/B == A つまり O(√T) < 10^4 にて計算できる。 // A,B > T のケースもあるので +1 して計算する ll ret = max((T/A+1)*A, (T/B+1)*B); for (ll m = 0; m <= min(T/B+1,A); ++m) { ll x = roundUp(T-m*B,A)*A + m*B; ret = min(ret,x); } cout<solve(); delete obj; return 0; } #endif