Under construction

Still being built. Things may change

God of Battle

Interview

Time limit1sMemory limit1024 MB

Summary
Given a budget N and two mercenary types with power A and B and costs PA and PB, find the counts x and y that maximize Ax+By within the budget.
Level

Medium5 of 10

Topics
Greedy, Brute force, Math
Solved
No attempts yet

Problem

Gisung has never lost a battle. Mingyeong, who loses every battle, kept begging Gisung to share the secret to winning. Tired of the pestering, Gisung told Mingyeong his own formula for choosing the mercenaries who join a battle. Mingyeong hires mercenaries according to that formula.

According to Gisung's formula, if one tanker has combat power AA and one dealer has combat power BB, Mingyeong hires xx tankers and yy dealers so that Ax+ByAx + By is maximized.

Mingyeong has only NN won to spend on hiring, so the hiring is limited. If hiring one tanker costs PAP_A and hiring one dealer costs PBP_B, write a program that finds how many tankers and how many dealers Mingyeong should hire.

Input

The first line contains NN, the amount of money Mingyeong can spend on hiring mercenaries. (1≤N≤10,000,000)(1 \leq N \leq 10{,}000{,}000)

The second line contains AA, PAP_A, BB, and PBP_B, separated by spaces. (1≤A,B≤10,000; 1≤PA,PB≤10,000,000)(1 \leq A, B \leq 10{,}000;\ 1 \leq P_A, P_B \leq 10{,}000{,}000)

All input values are integers.

Output

Print the number of tankers and the number of dealers to hire, separated by a space.

Examples1

  1. Example 1

    Input
    16
    7 2 9 4
    
    Expected output
    8 0