Maximum Product

Interview

Time limit2sMemory limit128 MB

Summary

Split S into K positive integers as equal as possible to maximize their product, given S and K up to 100 and 20.

Level: Easy3 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

Given integers S and K, choose K positive integers whose sum is S. Among all possible choices, find the maximum possible product of the chosen integers.

Input

The first line contains two integers S and K.

K is at most 20.
S is at most 100.
K is less than or equal to S.

Output

Print the maximum possible product. The answer is less than 9223372036854775807.

Examples5

Example 1
Input
```
10 3
```
Expected output
```
36
```
Example 2
Input
```
10 1
```
Expected output
```
10
```
Example 3
Input
```
10 10
```
Expected output
```
1
```
Example 4
Input
```
13 8
```
Expected output
```
32
```
Example 5
Input
```
7 2
```
Expected output
```
12
```