Келесі аптада сіз достарыңызбен демалысқа аттанасыз, бірақ алдымен азық-түлік сатып алу керек. Үнемдеу үшін барлық заттарды мейлінше арзан бағада сатып алғыңыз келеді.

Әрбір тауардың негізгі бағасы бар, сондай-ақ кейбір күндері оған жеңілдік беріледі. Сізге бір күнде дүкенге бару қажет, және барлық тауарларды сатып алғанда ең төменгі жалпы соманы таңдауыңыз керек.

Барлық тауарларды ең төменгі сомаға сатып алуға болатын күнді анықтаңыз.

Енгізу

Бір бүтін сан \(n\) — тауарлар саны \((1 \leq n \leq 10^5)\).

Одан кейін \(n\) тауардың сипаттамасы беріледі, әрбірі келесіден тұрады:

• Бір бүтін сан \(p_i\) — тауардың негізгі бағасы \((1 \leq p_i \leq 10^9)\), және бір бүтін сан \(m_i\) — тауардың жеңілдік алатын күндерінің саны \((0 \leq m_i \leq 7)\).

• Келесі \(m_i\) жолда екі бүтін сан беріледі:

  • \(d_j\) — жеңілдік күні \((1 \leq d_j \leq 7)\).

  • \(s_j\) — жеңілдік пайызы \((0 < s_j \leq 100)\).

Шығару

Бір сан — барлық тауарларды сатып алуға болатын минималды сома.

Жауапты төрт таңбалы дәлдікпен шығару қажет.

Мысалдар

Енгізу 1

3
100 2
1 10
3 20
200 1
2 30
150 3
1 10
4 50
6 20

Жауап 1

375.000000

Енгізу 2

2
500 3
2 10
3 15
6 5
400 2
3 30
4 20

Жауап 2

705.000000

Ескертпелер

Тауарлардың жеңілдіктері:

• Тауар 1 (100): \(\mathbf{10\%}\) жеңілдік дүйсенбіде, \(\mathbf{20\%}\) сәрсенбіде.

• Тауар 2 (200): \(\mathbf{30\%}\) жеңілдік сейсенбіде.

• Тауар 3 (150): \(\mathbf{10\%}\) жеңілдік дүйсенбіде, \(\mathbf{50\%}\) жеңілдік бейсенбіде, \(\mathbf{20\%}\) жеңілдік сенбіде.

Ең тиімді сатып алу күні: бейсенбі

Жауап: \(100 + 200 + 75 = 375\)