Vào năm 2206, để khuyến khích các coder vô cùng xuất sắc, HBCoder tổ chức một event trong vòng q ngày, vào ngày thứ i, với mỗi k_i bài tập được giải, coder sẽ được cộng thêm số điểm gấp đôi ở bài tập thứ k_{i + 1} (bài tập này không tính vào k_i bài tập tiếp theo). Lúc này, hệ thống HBCoder có n bài tập, bài tập thứ i giải đúng sẽ được p_i điểm.

Who you knows Who quyết định làm bài tập trên HBCCoder để cải thiện trình độ của mình. Tuy nhiên, vì bận leo rank Liên quân nên Who you knows Who chỉ có thể chọn 1 trong q ngày để leo rank HBCoder. Vì phong độ lúc lên lúc xuống nên vào ngày thứ i, phong độ của Who you knows Who chỉ cho phép anh ta giải được tối đa c_i bài tập.

Who you knows Who muốn tính xem làm bài vào ngày nào thì sẽ được cao điểm nhất, vì vậy anh ấy muốn biết nếu giải bài vào ngày thứ i, số điểm tối đa mà anh ấy có thể nhận được là bao nhiêu.

INPUT:

• Dòng đầu tiên gồm hai số nguyên dương n (1 <= n <= 10⁶) - số bài tập trên HBCoder và q (1 <= n <= 10⁶) - số ngày diễn ra event trên HBCoder.

• Dòng thứ hai gồm n số nguyên dương p₁, p₂,..., p_n (1 <= p<=10⁶) - số điểm nhận được nếu giải bài thứ i.

• q dòng tiếp theo, dòng thứ i gồm 2 số nguyên c_i và k_i (1<=c_i, k_i<=10⁶) - thể hiện ngày thứ i của event trong đề bài.

OUTPUT:

• Gồm q dòng, dòng thứ i in ra số điểm tối đa mà Who you knows Who nhận được nếu giải bài vào ngày thứ i.

​