Lắp ráp Lego


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Bin có một người bạn rất thích chơi lego nên muốn ra một câu đố. Bin đang có vô số mảnh lego với chiều rộng là \(1\) và có 2 loại chiều dài là \(a\) và \(b\).

Hãy giúp người bạn của Bin tìm số mảnh lego ít nhất mà có thể lắp được một hàng lego với chiều dài là \(n\) và chiều rộng là \(1\), nếu không có cách nào để lắp ráp hãy trả về \(-1\).

Input

  • Chứa 3 số nguyên \(a, b\) và \(n\) \((1 <= a,b,n <= 10^8)\)

Output

  • Số mảnh lego ít nhất để lắp ráp được một hàng lego với chiều dài \(n\). Nếu không có cách nào, in ra \(-1\)

Example

Input

1
3
10

Output

4

Giải thích:

  • Với \(a = 1, b = 3\) và \(n = 10\) thì cần 4 mảnh lego để lắp ráp. Vì, Ta sẽ cần 3 mảnh lego độ dài 3 và 1 mảnh lego độ dài 1 để lắp.

Comments

There are no comments at the moment.