Problem E
Skattaskrattar

Mynd fengin af flickr

Tökum dæmi, og segjum að það séu þrjú skattþrep:

Gefum okkar svo að manneskja fái $3000$ kr. í laun. Þessi laun falla alveg yfir fyrsta þrepið ($1000$ kr. á því þrepi), og að hluta til yfir annað þrepið ($2000$ kr. á því þrepi). Manneskjan borgar því $40\mathrm{\%}$ af fyrstu $1000$ krónunum af laununum, og svo $30\mathrm{\%}$ af næstu $2000$ krónunum af laununum. Samtals verða það því $0.4\cdot 1000+0.3\cdot 2000=1000$ krónur sem manneskjan þarf að borga.

Ef manneskjan hefði aftur á móti fengið $5500$ kr. í laun, þá hefðu launin alveg fallið yfir fyrsta þrepið ($1000$ kr. á því þrepi), alveg yfir annað þrepið ($4000$ kr. á því þrepi), og að hluta til yfir þriðja þrepið ($500$ kr. á því þrepi). Samtals verða það því $0.4\cdot 1000+0.3\cdot 4000+0.5\cdot 500=1850$ krónur sem manneskjan þarf að borga.

Árið er $3020$, og þó skýjakljúfar standi stoltir um Reykjavík og fljúgandi bílar leggi í svifbílastæði gegn vægu gjaldi, þá er enn í notkun sama skattakerfið. Skattþrepin eru þó orðin aðeins fleiri, eða $n$ talsins. Fyrsta skattþrepið gildir frá $0$ upp í $a_1$ krónur, annað skattþrepið frá $a_1$ upp í $a_2$ krónur, og svo framvegis upp í skattþrep númer $n$ sem gildir frá $a_{n-1}$ krónum og uppúr. Á fyrsta skattþrepinu þarf að borga $p_1\mathrm{\%}$ skatta, á öðru skattþrepinu $p_2\mathrm{\%}$ skatta, og svo framvegis upp í skattþrep númer $n$ þar sem þarf að borga $p_n\mathrm{\%}$ skatta.

Forseti Íslands hefur verið að íhuga hvernig skattþrepin fyrir árið $3021$ eiga að líta út. Hann er kominn með hugmynd að $m$ skattþrepum, og er þeim lýst eins og að ofan nema að skattþrepin eru táknuð með $b_i$ í stað $a_i$, og skattprósenturnar eru táknaðar með $q_i$ í stað $p_i$. Ef þessi skattþrep skildu vera notuð á næsta ári, þá hefur Forseti Íslands beðið þig að finna öll þau laun sem hann getur greitt starfsfólki sínu þannig að það borgi jafn mikinn skatt árið $3020$ og $3021$. Laun geta verið hvaða rauntölur sem eru, svo lengi sem þær séu ekki neikvæðar, en skattþrepin eru alltaf jákvæðar heiltölur.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $n$ og $m$ ($1\le n,m\le {10}^5$), fjöldi skattþrepa árið $3020$ og $3021$.

Næst koma $n$ línur sem tákna skattþrepin árið $3020$. Fyrstu $n-1$ línurnar innihalda tvær jákvæðar heiltölur $p_i$ og $a_i$. Síðan kemur ein lína með einni heiltölu $p_n$. ($0<p_i<100$ fyrir öll $i$)

Svo koma $m$ línur sem tákna skattþrepin árið $3021$. Fyrstu $m-1$ línurnar innihalda tvær jákvæðar heiltölur $q_i$ og $b_i$. Að lokum kemur ein lína með einni heiltölu $q_m$. ($0<q_i<100$ fyrir öll $i$)

Skattþrepin eru gefin í hækkandi röð, þ.e. $a_i<a_{i+1}$ og $b_i<b_{i+1}$, og ekkert skattþrep fer yfir ${10}^5$ krónur, þ.e. $a_{n-1},b_{m-1}\le {10}^5$.

Úttak

Úttakið skal innihalda öll þau laun sem borga sama skatt í báðum skattkerfunum, í hækkandi röð. Ef laun $x$ borga sama skatt í báðum skattkerfum er gefið að engin laun á bilinu $[x-{10}^{-4},x+{10}^{-4}]$ borgi líka sama skatt í báðum skattkerfum.

Úttakið er talið rétt ef hver tala er annaðhvort nákvæmlega eða hlutfallslega ekki lengra frá réttu svari en ${10}^{-4}$. Þetta þýðir að það skiptir ekki máli með hversu margra aukastafa nákvæmni tölurnar eru skrifaðar út, svo lengi sem þær er nógu nákvæmar.

Stigagjöf

3 2
40 1000
30 5000
50
20 500
80

0.000000000000000
750.000000000000000

2 3
71 14
42
43 5
6 49
20

0.000000000000000

5 5
86 874
10 2170
18 5738
99 5891
76
98 497
31 3229
75 7670
58 8394
60

0.000000000000000
605.436363636363581
1577.380952380952294
17815.375000000003638