Find minimum number of coins required to form any value between 1 to N, both inclusive. Cumulative value of coins should not exceed N. Coin denominations are 1 Rupee, 2 Rupee and 5 Rupee.

Lets understand the problem using the following example.

Consider value of N is 13, then the minimum number of coins required to formulate any value between 1 and 13, is 6. One 5 Rupee, three 2 Rupee and two 1 Rupee coins are required to realize any value between 1 and 13. Hence this is the answer.

However, if one takes two 5 Rupee coins, one 2 rupee coin and two 1 rupee coin, then too all values between 1 and 13 are achieved. But since the cumulative value of all coins equals 14, i.e., exceeds 13, this is not the answer.

Constraints

0 < n < 100000

Input Format

A single integer value.

Output

Four space separated integer values.

1st – Total number of coins.

2nd – number of 5 Rupee coins.

3rd – number of 2 Rupee coins.

4th – number of 1 Rupee coins.

Test Case

Input

13

Output

6 1 3 2

Explanation

The minimum number of coins required is 6 with in it:

minimum number of 5 Rupee coins = 1

minimum number of 2 Rupee coins = 3

minimum number of 1 Rupee coins = 2

Using these coins, we can form any value with in the given value and itself, like below:

Here the given value is 13

For 1 = one 1 Rupee coin

For 2 = one 2 Rupee coin

For 3 = one 1 Rupee coin and one 2 Rupee coins

For 4 = two 2 Rupee coins

For 5 = one 5 Rupee coin

For 6 = one 5 Rupee and one 1 Rupee coins

For 7 = one 5 Rupee and one 2 Rupee coins

For 8 = one 5 Rupee, one 2 Rupee and one 1 Rupee coins

For 9 = one 5 Rupee and two 2 Rupee coins

For 10 = one 5 Rupee, two 2 Rupee and one 1 Rupee coins

For 11 = one 5 Rupee, two 2 Rupee and two 1 Rupee coins

For 12 = one 5 Rupee, three 2 Rupee and one 1 Rupee coins

For 13 = one 5 Rupee, three 2 Rupee and two 1 Rupee coins

public class HelloWorld{

public static void main(String []args){

int five=0;

int one=0;

int two=0;

int number=3;

int original=number;

int dummy=number;

while(((dummy-4)%5)!=0){

dummy– ;

}

five=(dummy-4)/5;

if(five<0)

five=0;

number=number-(5*five);

if(number%2==0){

one=2;

}

else{

one=1;

}

two=(original-(one+(5*five)))/2;

System.out.println("ones="+ one+" twos= "+two+" FIVES= "+five);

}

}

what logic are you using to calculate the no of rs 5 coins?

lol very simple

n = int(input())

five = two = one = 0

temp = n

while temp % 5 != 0:

temp -= 1

five = (temp//5) – 1

temp = n – (5*five)

if temp % 2 == 0:

one = 2

else:

one = 1

temp -= one

two = temp//2

print((five+two+one), five, two, one)