Under construction

Still being built. Things may change

Kate's 2021 Celebration

Interview

Time limit2sMemory limit512 MB

Summary
Given packs of balloons, each with a price and a digit string, find the cheapest single pack that contains the digits 2, 0, 2, 1.
Level

Easy3 of 10

Topics
Implementation, String, Sorting, Greedy
Solved
No attempts yet

Problem

Kate did not have a good year in 2020, and she is glad that it is coming to an end. She is planning to celebrate New Year 2021 on a grand scale.

Kate has decided to buy four balloons with the digits 2 0 2 1 painted on them for her 2021 celebration. She went to a store's web site and found that balloons with digits are sold in packs containing different assortments of balloons of various sizes, colors, and with different digits painted on them. Kate does not care about their size, color, or other attributes. She only cares about the digits written on those balloons. Fortunately, the store has all the information about the different packs of balloons that are available. Kate managed to retrieve it through the store's REST API and extracted just the information she needs: the price and the digits written on the balloons in each pack.

Help Kate with the final task of figuring out the cheapest pack of balloons she can buy that would get her the four digits she needs for her 2021 celebration.

Input

The first line of the input file contains an integer nn (1≤n≤10001 \le n \le 1000), the number of packs of balloons available in the store.

The next nn lines contain descriptions of packs, one line per pack. Each pack is described by an integer pp (1≤p≤1051 \le p \le 10^5), the price of the pack in roubles, followed by a string of at least one and at most 100 digits (each digit is from 0 to 9), the digits on the balloons in the pack.

Output

Output a single integer: the number of the cheapest pack that Kate can buy to get the digits for her 20212021 celebration. Packs of balloons are numbered starting from 11 in the order they are given in the input. If there are multiple packs with the same price, output any one of them.

Output 00 if there is no pack in the store that Kate can buy for her 2021 celebration.

Hint

In the first example, the 2nd and 3rd packs of balloons contain the digits 2 0 2 1, and the 3rd one is the cheapest.

Examples2

  1. Example 1

    Input
    4
100 9876543210
200 00112233445566778899
160 012345678924568
150 000000123456789
    Expected output
    3

  2. Example 2

    Input
    5
100 0123456789
120 0022446688
200 00224466883456789
10 0
10 1
    Expected output
    0