Club Cheer Volume

Interview

Time limit1sMemory limit256 MB

Summary

Given N ideal volumes, find the smallest shout volume D so that at least K members reach satisfaction at least X percent, and print D as an integer or reduced fraction.

Level: Medium6 of 10
Topics: Math, Number theory, Sorting, Binary search
Solved: No attempts yet

Problem

Jinyoung has become the president of his club and wants to show his resolve at the club dinner by shouting louder than anyone else. However, when he shouts the cheer P!D!A! Oh! P!D!A! Oh!, each club member has a different idea of the appropriate volume, so some members may think Jinyoung's voice is too quiet while others think it is too loud. In the end, Jinyoung wants to shout at the smallest volume such that at least K members have a satisfaction of at least X. Let D be Jinyoung's volume and let Pi be the volume that member i considers appropriate. The satisfaction of member i is defined as follows.

satisfaction = {(Pi - |Pi - D|) / Pi} * 100

Write a program that finds the smallest volume such that at least K members have a satisfaction of at least X.

Input

The first line contains the integers N (1 ≤ N ≤ 105), X (1 ≤ X ≤ 100), and K (1 ≤ K ≤ N), separated by spaces.

The second line contains N integers Pi (1 ≤ Pi ≤ 105), separated by spaces, where Pi is the volume that member i considers appropriate.

Output

Let ANS be the smallest volume such that at least K members have a satisfaction of at least X. If ANS is an integer, print the integer value; otherwise, print it as a reduced fraction in the form p/q. If no such ANS exists, print -1.

Examples3

Example 1
Input
```
5 70 3
70 65 80 50 100
```
Expected output
```
49
```
Example 2
Input
```
5 70 2
70 65 80 50 100
```
Expected output
```
91/2
```
Example 3
Input
```
5 70 5
70 65 80 50 100
```
Expected output
```
-1
```