news reporter

Time Limit: 1500 ms Memory Limit: 65536 KiB

Problem Description

There are n(1≤n≤5000) big events happened in the community, with the ith event a postive energy value ai and a negative energy value bi. As an experienced news reporter, you want to choose at least K events e1,e2,...,eK and maximize harmonious value

 H=.

It is guaranteed that there are at most K−1 events whose negative energy value is 0.
Better yet, you have just learned how to increase the base of positive energy, which means you can add an integer c(c>0) to all the events' positive energy value at your will. You think that skill can make harmonious value even bigger.
However, the public is aware of your trick. If the harmonious value is too big (greater or equal to lim), they will regard H as H mod lim. So be careful to use your trick, if your report deviates you will have to take responsibility!

Input

Multiple test cases. For each case:

  • The first line contains three integers n,K,lim(1≤Kn≤5000,1≤lim≤10^6);
  • The second line contains n integers a1,a2,..,an(0≤ailim);
  • The third line contains n integers b1,b2,..,bn(0≤bilim);

Output

For each test case, output a real number in a single line, indicating the maximum value of H. Keep 7 decimal places.

Sample Input

5 3 10
1 2 3 4 5
1 2 3 4 5

Sample Output

4.0000000

Hint

Source

“浪潮杯”山东省第八届ACM大学生程序设计竞赛(感谢青岛科技大学)