시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 62 8 7 14.286%

문제

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

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

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

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

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

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

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

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

입력

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

출력

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

예제 입력

3 1
100 2
100 3
50 1

예제 출력

2.000

힌트

출처

  • 문제를 만든 사람: xhark