Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.
Ограничения: 1 <=M, N, T, <= 1000000 , все числа целые.
Входные данные
В первой строке находятся три числа - M, N и T, разделённые пробелами.
Выходные данные
Вывести максимальное суммарное число гамбургеров и чизбургеров. Если остаётся какое-то время, требуется указать его через пробел. Предпочтителен вариант, когда дополнительного времени остаётся как можно меньше.
| Ввод |
Вывод |
| 1 2 1000 |
1000 |
| 2 1 1000 |
1000 |
| 3 6 1000 |
333 1 |