Та морь унасан баавгайнуудын эсрэг тулалдахыг хүсэж байна уу? Би ч бас хүсэхгүй байна.

Лимак бол хүрэн баавгай. Тэрээр Беэрландын аймшигтай армийн генерал. Уг армийн хамгийн чухал хэсэг нь мэдээж морин цэрэг юм.

Беэрландын морин цэрэг нь $n$ дайчин болон $n$ морьдоос тогтоно. $i$-дахь дайчин нь $w_{i}$ хүчтэй ба $i$-дахь морь нь $h_{i}$ хүчтэй. Дайчныг түүний морьтой нь хамтад нь нэг нэгж гэж нэрлэнэ. Нэг нэгжийн хүч нь дайчин болон морь хоёрын хүчийг үржүүлсэнтэй тэнцүү байх юм. Морин цэргийн нийт хүч нь бүх $n$ нэгжүүдийн хүчний нийлбэртэй тэнцүү байна. Дайчид болон морьдын сайн хослолт нь үнэхээр хүчирхэг морин цэргийг бий болгох юм.

Анхандаа, $i$-дахь дайчин нь $i$-дахь морьтой байна. Танд $q$ ширхэг асуулт өгөгдөнө. Асуулт бүрийн хувьд 2 дайчин нь бие биетэйгээ морио солих юм.

Генерал Лимак бүх боломжит нөхцөл байдалд бэлэн байх ёстой. Хэрэв дайчид нь тэдгээрийн өөрсдийн морио унах нь зөвшөөрөгдөөгүй бол яах вэ? Асуулт бүрийн дараах хэрэв бид нэг ч дайчин нь өөрийнхөө морьтойгоо хослоогүй байхаар бүх дайчдыг бүх моринд хослуулна гэж үзэхэд үүсэх морин цэргийн боломжит хамгийн их хүчийг олно уу ($n ≥ 2$ бүрийн хувьд үргэлж ядаж ганц зөв хослолт байна.).

Бид дайчныг морьгүй үлдээж болохгүйг анхаарна уу.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $n$ болон $q$ ($2 ≤ n ≤ 30 000$, $1 ≤ q ≤ 10 000$) өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоо $w_{1}, w_{2}, ..., w_{n}$ ($1 ≤ w_{i} ≤ 10^{6}$) өгөгдөнө -- эдгээр нь дайчдын хүчийг илэрхийлнэ.

3-дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоо $h_{1}, h_{2}, ..., h_{n}$ ($1 ≤ h_{i} ≤ 10^{6}$) өгөгдөнө -- эдгээр нь морьдын хүчийг илэрхийлнэ.

Дараагийн $q$ мөрөнд асуултуудыг дүрсэлнэ. Тэдгээрийн $i$-дахь нь зайгаар тусгаарлагдсан 2 бүхэл тоо $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$)-г агуулна, эдгээр нь морьдоо солих дайчдын индексүүдийг илэрхийлнэ.

Гаралт

Асуултуудын хариултуудыг $q$ мөрөнд хэвлэнэ. $i$-дахь мөрөнд эхний $i$ асуултын дараах морин цэргийн боломжит хамгийн их хүчийг хэвлэнэ.

Эхний жишээний тодруулга:

Дайчид: 1 10 100 1000

Морьд:   3  7  2    5 

Эхний асуултын дараа нөхцөл байдал дараах байдлаар харагдана:

Дайчид: 1 10 100 1000

Морьд:   3  5  2    7 

Бид $1*2 + 10*3 + 100*7 + 1000*5 = 5732$-тай болно (энэ хослолтонд ямар ч морьтон өөрийн морьтойгоо хослоогүй байгааг анхаарна уу).

2-дахь асуултын дараа бид анхны нөхцөл байдалдаа очих ба тохиромжтой хослолт нь $1*2 + 10*3 + 100*5 + 1000*7 = 7532$ байна.

2-дахь жишээний тодруулга. Эхний асуултын дараа:

Дайчид:  7 11 5

Морьд:    2  3 1

Оновчтой хослуулалт нь $7*1 + 11*2 + 5*3 = 44$ байна.

2-дахь асуултын дараа оновчтой хослуулалт нь $7*3 + 11*2 + 5*1 = 48$ байна.

Эцэст нь оновчтой хослуулалт нь $7*2 + 11*3 + 5*1 = 52$ байх юм.