#line 2 "/home/cocojapanpan/Procon_CPP/proconLibrary/lib/template/procon.hpp" #ifndef DEBUG // 提出時にassertはオフ #ifndef NDEBUG #define NDEBUG #endif // 定数倍高速化 #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include using namespace std; using ll = long long; #define ALL(x) (x).begin(), (x).end() template using vec = vector; template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } template constexpr T INF = 1'000'000'000; template <> constexpr int INF = 1'000'000'000; template <> constexpr ll INF = ll(INF) * INF * 2; #line 2 "main.cpp" int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vec A(N), B(N); ll A_sum = 0, B_sum = 0; for(int i = 0; i < N; i++) { cin >> A[i] >> B[i]; A_sum += A[i]; B_sum += B[i]; } // 残ったAの和*Bi vs Ai*残ったBの和 // 前者が大きいなら前におく vec P(N); { int front = 0, back = N - 1; for(int i = 0; i < N - 1; i++) { A_sum -= A[i]; B_sum -= B[i]; if(A_sum * B[i] > A[i] * B_sum) { P[i] = front; ++front; } else { P[i] = back; --back; } } assert(front == back); P[N - 1] = front; } vec inv_P(N); for(int i = 0; i < N; i++) { inv_P[P[i]] = i; } ll score = 0; { ll preB_sum = 0; for(int i = 1; i < N; i++) { preB_sum += B[inv_P[i - 1]]; score += A[inv_P[i]] * preB_sum; } } cout << score << "\n"; }