Hamburger Love

Time limit2sMemory limit128 MB

Summary

Given eating times n and m for two burger types and a total time t, find the maximum number of burgers eaten (minimizing leftover cola time, then maximizing count) subject to n*a+m*b <= t.

Level: Medium5 of 10
Topics: Math, Brute force, Number theory
Solved: No attempts yet

Problem

Minhyuk likes two kinds of hamburgers. It takes him n minutes to eat one hamburger of the first kind and m minutes to eat one hamburger of the second kind.

He wants to spend a total of t minutes eating hamburgers. If he starts eating a hamburger, he must finish it before the t minutes end. During any remaining time when he is not eating a hamburger, he drinks cola.

Choose a plan by the following rules.

Make the cola-drinking time as small as possible.
If several plans have the same cola-drinking time, choose one that eats the largest number of hamburgers.

Input

The first line contains n, m, and t, separated by spaces. All three numbers are positive integers no greater than 10,000.

Output

Output two integers on one line, separated by a space. The first integer is the number of hamburgers eaten, and the second integer is the time spent drinking cola.

Examples4

Example 1
Input
```
3 5 55
```
Expected output
```
17 0
```
Example 2
Input
```
3 5 54
```
Expected output
```
18 0
```
Example 3
Input
```
3 5 7
```
Expected output
```
2 1
```
Example 4
Input
```
3 5 8
```
Expected output
```
2 0
```