This page is still under construction.

Parts of this page are still being built. What you see may change.

Stars on Shoulder Boards

Time limit2sMemory limit512 MB

Summary
Given bounds on star counts and the min and max stars removable from officer Y, find the smallest and largest possible battalion size.
Level

Medium5 of 10

Topics
Math, Implementation, Brute force, Intervals
Solved
No attempts yet

Problem

In a battalion of unclear purpose, a rule holds that every officer must have at least aa and at most bb stars on his shoulder boards, and no two officers may have the same number of stars.

As a result of a demotion, an officer Й was transferred to this battalion. Before the demotion, officer Й had cc stars on his shoulder boards. The battalion commander must now remove some of the stars from Й's shoulder boards, so that the number of stars on them becomes strictly less than cc.

The battalion commander looked into the matter and found that the smallest positive number of stars that can be removed from officer Й's shoulder boards so that the rule holds is dd, and the largest is ee. The commander immediately reported this to officer Й.

Officer Й now wonders: what is the smallest and the largest number of officers that could have been in the battalion before his arrival? The battalion commander is not an officer of the battalion, and his shoulder boards bear special mysterious symbols instead of stars.

Input

The first line contains five integers aa, bb, cc, dd, ee (1≤a,b,c,d,e≤10001 \le a, b, c, d, e \le 1000, a≤ba \le b, a<ca < c, d≤ed \le e).

The situation is guaranteed to be consistent: officer Й can be demoted so that the rule stated in the problem holds, and the commander's statement is true.

Output

Output the smallest and the largest possible number of officers in the battalion.

Examples2

  1. Example 1

    Input
    10 18 20 5 8
    
    Expected output
    5 7
    
  2. Example 2

    Input
    2 10 5 1 3
    
    Expected output
    0 7