Bài 5: (2 điểm) - XẾP HÀNG

Trường THPT chuyên XYZ có n học sinh đang xếp thành một hàng dọc. Các học sinh được đánh số từ 1 đến n. Ban đầu, học sinh I đứng ở vị trí thứ I trong hàng. Mỗi học sinh I có hai giá trị đặc trưng là a_i và b_i. Độ không hài lòng của học sinh I bằng tích của a_i và số lượng học sinh đứng bên trái học sinh I cộng với tích của b_i và số lượng học sinh đứng bên phải học sinh i. Một cách tổng quát, nếu học sinh I đứng ở vị trí thứ j, độ không hài lòng của học sinh này là a_i*(j−1)+b_i*(n−j); Hiệu trưởng giao cho bạn nhiệm vụ là tìm một cách xếp hàng sao cho tổng độ không hài lòng của tất cả học sinh là nhỏ nhất có thể.

Dữ liệu: từ file BAI5.INP

+ Dòng đầu tiên chứa một số nguyên n (1≤n≤10⁵) – số học sinh trong hàng đợi

+ Mỗi dòng trong n dòng sau chứa hai số nguyên a_i và b_i (1≤a_i, b_i ≤10⁸) – hai giá trị đặc trưng của học sinh i.

Kết quả: ghi ra file BAI5.OUT: một số nguyên duy nhất là tổng độ hài lòng nhỏ nhất tìm được.