Colorful Beans

AtCoder

IDabc348_c

Time2000ms

Memory256MB

Difficulty—

There are $N$ types of beans, one bean of each type. The $i$\-th type of bean has a deliciousness of $A_i$ and a color of $C_i$. The beans are mixed and can only be distinguished by color. You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat. ## Constraints * $1 \leq N \leq 2 \times 10^{5}$ * $1 \leq A_i \leq 10^{9}$ * $1 \leq C_i \leq 10^{9}$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $A_1$ $C_1$ $A_2$ $C_2$ $\vdots$ $A_N$ $C_N$ [samples]

Samples

Input #1

Output #1

40

Note that beans of the same color cannot be distinguished from each other.
You can choose color $1$ or color $5$.

*   There are two types of beans of color $1$, with deliciousness of $100$ and $40$. Thus, the minimum deliciousness when choosing color $1$ is $40$.
*   There are two types of beans of color $5$, with deliciousness of $20$ and $30$. Thus, the minimum deliciousness when choosing color $5$ is $20$.

To maximize the minimum deliciousness, you should choose color $1$, so print the minimum deliciousness in that case: $40$.

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Colorful Beans",
    "description": {
      "content": "There are $N$ types of beans, one bean of each type. The $i$\\-th type of bean has a deliciousness of $A_i$ and a color of $C_i$. The beans are mixed and can only be distinguished by color. You will ch",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc348_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ types of beans, one bean of each type. The $i$\\-th type of bean has a deliciousness of $A_i$ and a color of $C_i$. The beans are mixed and can only be distinguished by color.\nYou will ch...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments