1381번 - 요구르트의 유통기한 채점 준비 중

요구르트 여러개가 모두 유통기한이 1/15이다! 고로 임현수는 이 요구르트들을 모두 먹어 치우려고 한다.

문제는 혼자서 요구르트를 먹는데에는 한계가 있다라는 사실이다. 하지만 임현수는 언제나 요구르트를 먹을 때 마다 ‘언젠가는 배터지게 요구르트를 먹어서, 얼만큼 먹을 수 있나 알아보고 싶다’라는 소망을 가지고 있었기에 그에게 있어서 이번 일은 기회가 아닐 수 없다.

총 n개의 요구르트가 있다. 임현수는 이 요구르트 들을 모두 마시고 싶다. 그런데 알고보니 요구르트들의 무게가 미묘하게 달랐다. 임현수는 이 중에서 k개의 요구르트를 먹고 싶다.

문제는 애석하게도 요구르트에는 불량품일 확률이 있다. 만약 불량품을 마신다면 임현수는 정신을 잃고 지민이를 납치할 것이다.

하지만 그 확률이 매우 미미하기 때문에 임현수는 그저 가장 많은 요구르트를 마시고 싶다.

하지만, 지민이는 민식이꺼다.

민식이는 지민이를 뺏기기 싫기 때문에 임현수에게 “n개중에 k개를 마실 때 가장 많은 양의 요구르트를 마시면서 지민이가 납치될 확률이 가장 적은” 요구르트 집합을 주기로 했다.

이때, 지민이가 납치될 확률을 구하여라.

첫째 줄에는 요구르트의 개수 n(1 ≤ n ≤ 1,000,000)과 먹고싶은 요구르트의 개수 k(1 ≤ k ≤ n)가 주어진다. 2번째 줄에서 n+1번째 줄에는 각각의 줄마다 i번째 요구르트의 양 U_i(1 ≤ U_i ≤ 1,000,001)과 그 요구르트가 불량품일 확률 P_i %(0 ≤ P_i ≤ 10)가 주어진다. 모든 입력은 정수로 주어진다.

지민이가 납치될 %확률을 “.3lf"의 형태로 출력한다. 만약 지민이가 납치될 확률이 소수점 4째자리에서 반올림해서 0.001미만 이라면 “GG”를 출력한다.