The Holidays Are Coming
Limits: 2 sec., 256 MiB
We can often hear the saying “The holidays are coming”, but have you ever thought about how are they coming? And here is the answer: they are coming with bag on the back and well known song in the air. Yes, it is Santa Claus coming to cheer up all the kids with some nice presents.
In the village with no name there is one long street with \(N\) houses. Santa starts with the first house on the street and comes in every one until he visits all of them. Somewhere the distance between two neighboring houses is too long and Santa has very boring way from one house to another. That’s why the council of the village decided to build \(M\) new houses on the street in the way to minimize the longest distance between the neighboring houses. You have to find the longest distance between the neighboring houses after the new \(M\) houses will be built.
Input
The first line contains two integer numbers \(N\) and \(M\) separated by a single space. The next line contains \(N-1\) integer numbers \(d_i\) separated by single spaces. Here, \(d_i\) is a distance between the \(i\)-th and the \((i+1)\)-th houses on the street.
Output
Print the longest distance between the neighboring houses as an irreducible fraction in \(a/b\) form, where \(0 \le a\) and \(0 < b\).
Constraints
\(2 \le N \le 100000 (10^5)\),
\(1 \le M \le 100000 (10^5)\),
\(1 \le d_i \le 1000000000 (10^9)\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 4 7 1 3 | 7/4 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|