Sugar Water 2

AtCoder

IDabc294_f

Time4000ms

Memory256MB

Difficulty—

Takahashi and Aoki have $N$ and $M$ bottles of sugar water, respectively. Takahashi's $i$\-th sugar water is composed of $A_i$ grams of sugar and $B_i$ grams of water. Aoki's $i$\-th sugar water is composed of $C_i$ grams of sugar and $D_i$ grams of water. There are $NM$ ways to choose one from Takahashi's sugar waters and one from Aoki's and mix them. Among the $NM$ sugar waters that can be obtained in this way, find the concentration of sugar in the sugar water with the $K$\-th highest concentration of sugar. Here, the concentration of sugar in sugar water composed of $x$ grams of sugar and $y$ grams of water is $\dfrac{100x}{x+y}$ percent. We will ignore saturation. ## Constraints * $1 \leq N, M \leq 5 \times 10^4$ * $1 \leq K \leq N \times M$ * $1 \leq A_i, B_i, C_i, D_i \leq 10^5$ * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $K$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$ $C_1$ $D_1$ $C_2$ $D_2$ $\vdots$ $C_M$ $D_M$ [samples]

Samples

Input #1

Output #1

50.000000000000000

Let $(i, j)$ denote the sugar water obtained by mixing Takahashi's $i$\-th sugar water and Aoki's $j$\-th.  
Below are the sugar waters that can be obtained and their concentrations of sugar.

*   $(1, 1)$ : $100 \times \frac{1 + 1}{(1 + 1) + (2 + 4)} = 25 \%$
*   $(2, 1)$ : $100 \times \frac{1 + 4}{(4 + 1) + (1 + 4)} = 50 \%$
*   $(3, 1)$ : $100 \times \frac{1 + 1}{(1 + 1) + (4 + 4)} = 20 \%$

Among them, the sugar water with the highest concentration of sugar is $(2, 1)$, with a concentration of $50$ percent.

Input #2

Output #2

62.500000000000000

Input #3

Output #3

54.166666666666664

API Response (JSON)

{
  "problem": {
    "name": "Sugar Water 2",
    "description": {
      "content": "Takahashi and Aoki have $N$ and $M$ bottles of sugar water, respectively.   Takahashi's $i$\\-th sugar water is composed of $A_i$ grams of sugar and $B_i$ grams of water.   Aoki's $i$\\-th sugar water i",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc294_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi and Aoki have $N$ and $M$ bottles of sugar water, respectively.  \nTakahashi's $i$\\-th sugar water is composed of $A_i$ grams of sugar and $B_i$ grams of water.  \nAoki's $i$\\-th sugar water i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments