C. Бөмбөг сонгох

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$n$ ширхэг бөмбөг байна. Тэд нэг мөрөнд байрласан байна. Бөмбөг бүр өнгөтэй ба бүхэл тоон утгатай. $i$-р бөмбөгийн өнгө $c_{i}$ ба $i$-р бөмбөгийн утга нь $v_{i}$ юм.

Скүрл Лис хэдэн бөмбөг сонгох ба авсан бөмбөгнүүдийн анх байсан дарааллыг өөрчлөхгүйгээр шинэ дараалал үүсгэнэ. Скүрл Лис энэ дарааллын утгыг хамгийн их байлгахыг хүснэ.

Дарааллын утга нь бөмбөг бүрийн утгын нийлбэр юм. Бөмбөг бүрийн утга дараах байдлаар тодорхойлогдоно (энд $a$,$b$ нь өгөгдсөн тогтмол тоо):

  • Хэрвээ бөмбөг дарааллын эхний бөмбөг биш ба бөмбөгийн өнгө нь өмнөх бөмбөгтэй ижил бол бөмбөгийн шинэ утга нь $v_{i} × a$ болно.
  • Бусад тохиолдолд бөмбөгийн шинэ утга нь $v_{i} × $ $b$ болно.

Танд $q$ ширхэг асуумж өгөгдөх ба асуумж бүр $a_{i}$ болон $b_{i}$ гэсэн хоёр бүхэл тоон утга агуулна. Асуумж бүрийн хувьд $a = a_{i}$ болон $b = b_{i}$ үеийн Скүрл Лисийн бүтээж чадах дарааллын хамгийн их утгыг олно.

Мөн шинээр үүсч буй дараалал хоосон байж болох ба энэ дарааллын утга 0-ээр тооцогдоно.

Оролт

Оролтын эхний мөр $n$ болон $q$ ($1 ≤ n ≤ 10^{5}; 1 ≤ q ≤ 500$) хоёр бүхэл тоон утга агуулна. Хоёр дахь мөр $n$ ширхэг бүхэл тоон утгууд болох $v_{1}, v_{2}, ..., v_{n}$ ($|v_{i}| ≤ 10^{5}$)-г агуулна. Дараагийн $q$ мөрөнд асуумж бүрийн $a$ болон $b$ тогтмолуудыг агуулна. Эдгээр мөрүүдийн $i$-р мөр бүр $a_{i}$ болон $b_{i}$ ($|a_{i}|, |b_{i}| ≤ 10^{5}$) гэсэн хоёр бүхэл тоон утга агуулна.

Мөр бүрийн бүхэл тоон утгууд зайгаар тусгаарлагдана.

Гаралт

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

C++ хэл дээр 64 битийн бүхэл тоог унших болон бичихдээ %lld тодорхойлогчийг битгий ашиглаарай. Харин cin, cout урсгалууд эсвэл %I64d тодорхойлогчийг ашиглаарай.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
6 3
1 -2 3 4 0 -1
1 2 1 2 1 1
5 1
-2 1
1 0
Гаралт
20
9
4
Оролт
4 1
-3 6 -1 2
1 2 3 1
1 -1
Гаралт
5

Тэмдэглэл

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

  • Эхний асуумж дээр 1, 3 болон 4-р бөмбөгийг сонгоно.
  • Хоёр дахь асуумж дээр 3, 4, 5 болон 6-р бөмбөгийг сонгоно..
  • Гурав дахь асуумж дээр 2 болон 4-р бөмбөгийг сонгоно.

Хамгийн их утгыг олох өөр арга зам байж болно гэдгийг сана.

Сэтгэгдлүүдийг ачааллаж байна...