{"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 is composed of $C_i$ grams of sugar and $D_i$ grams of water.  \nThere 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.  \nHere, 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.\n\n## Constraints\n\n*   $1 \\leq N, M \\leq 5 \\times 10^4$\n*   $1 \\leq K \\leq N \\times M$\n*   $1 \\leq A_i, B_i, C_i, D_i \\leq 10^5$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_N$ $B_N$\n$C_1$ $D_1$\n$C_2$ $D_2$\n$\\vdots$\n$C_M$ $D_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc294_f","tags":[],"sample_group":[["3 1 1\n1 2\n4 1\n1 4\n1 4","50.000000000000000\n\nLet $(i, j)$ denote the sugar water obtained by mixing Takahashi's $i$\\-th sugar water and Aoki's $j$\\-th.  \nBelow are the sugar waters that can be obtained and their concentrations of sugar.\n\n*   $(1, 1)$ : $100 \\times \\frac{1 + 1}{(1 + 1) + (2 + 4)} = 25 \\%$\n*   $(2, 1)$ : $100 \\times \\frac{1 + 4}{(4 + 1) + (1 + 4)} = 50 \\%$\n*   $(3, 1)$ : $100 \\times \\frac{1 + 1}{(1 + 1) + (4 + 4)} = 20 \\%$\n\nAmong them, the sugar water with the highest concentration of sugar is $(2, 1)$, with a concentration of $50$ percent."],["2 2 2\n6 4\n10 1\n5 8\n9 6","62.500000000000000"],["4 5 10\n5 4\n1 6\n7 4\n9 8\n2 2\n5 6\n6 7\n5 3\n8 1","54.166666666666664"]],"created_at":"2026-03-03 11:01:14"}}