Олимпиадный тренинг

Задача 33650. Homer Simpson


Задача

Темы: Задача о рюкзаке
Homer Simpson's lunch break is T milliseconds. Homer eats one hamburger in N milliseconds, one cheeseburger in M. How many hamburgers and cheeseburgers should be eaten so that the time spent is as large as possible without exceeding T. If the time spent is equal, it is necessary to maximize the total number of hamburgers and cheeseburgers eaten.

Limits: 1 <=M, N, T, <= 1000000 , all integers.

Input
The first line contains three numbers - M, N and T, separated by spaces.

Imprint
Output the maximum total number of hamburgers and cheeseburgers. If there is some time left, you need to specify it separated by a space. The preferred option is when there is as little extra time left as possible.
 
Input Output
1 2 1000 1000
2 1 1000 1000
3 6 1000 333 1