Lộc 2025

Tết đến là dịp gia đình được sum vầy, người người tấp nập náo nức du xuân, khai lộc đầu năm, gửi gắm tới năm mới những mục tiêu và ước mơ xa hơn.

Quan trọng hơn, Đạt nhận được rất nhiều lì xì trong năm này, nhưng đồng thời cũng cho đi rất nhiều lộc. Gọi \(N\) là số người Đạt đã cho/nhận lì xì, số tiền mà Đạt đã nhận được trong năm mới Ất Tỵ 2025 là:

Hãy giúp Đạt tính số tiền nhận được trong Tết này để quyết định có nên du xuân hay ở nhà không nhé!

Input

• Một dòng duy nhất chứa số nguyên dương \(N\) \((1 \le N \le 10^9)\).

Output

• Một số nguyên thể hiện lượng tiền Đạt nhận được - kết quả của biểu thức trên.

Scoring

• Subtask \(1\) \((70\%)\): \(1 \le N \le 10^6\).
• Subtask \(2\) \((30\%)\): \(1 \le N \le 10^9\).

Sample

3

-6

4

10

Chắc hẳn các bạn đã quen với trò "Bầu cua tôm cá" rồi nhỉ? Luật chơi vô cùng đơn giản:

Có 6 linh vật: bầu - cua - cá - gà - tôm - nai. Người quản trò sẽ lắc 3 viên xúc xắc đồng thời và giữ kín kết quả. Sau đó, người chơi sẽ có quyền đặt cược vào một hay nhiều linh vật kể trên. Khi đặt xong, người quản trò sẽ công bố kết quả xúc xắc.

Nếu trong ba viên xúc xắc xuất hiện linh vật mà người chơi đã đặt cược tiền, họ sẽ lấy lại tiền cược và người quản trò phải trả số tiền bằng với số lần linh vật đó xuất hiện nhân với số tiền cược. Nếu linh vật người chơi chọn không xuất hiện, số tiền đặt cược thuộc về người quản trò.

Tuy nhiên, Đạt - người nắm trong tay quyền quản trò, muốn thu thêm một tí lợi nhuận. Đạt sẽ thay đổi luật chơi trò này đi một chút: cho \(n\) linh vật, \(k\) viên xúc xắc nhiều mặt, người chơi chỉ được phép đặt vào một linh vật, và số tiền thu được của người chơi sẽ là:

tiền cược \(*\) số viên xúc xắc trúng linh vật cược \(-\) tiền cược \(*\) số viên xúc xắc KHÔNG trúng linh vật cược.

Giả sử bạn là người chơi của trò quỷ quái này, và số tiền cược bạn đặt vào nếu cược linh vật \(i\) là \(c_i\), hãy tính số tiền lớn nhất mà bạn có thể nhận được trong trường hợp may mắn nhất. Lưu ý: bạn bắt buộc phải chơi : D, không có quyền không cược.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, k\) \((1 \le n, k \le 2 * 10^5)\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(c_i\) - số tiền bạn cược vào linh vật \(i\) nếu chọn linh vật này \((1 \le c_i \le 10^9)\).
• \(k\) dòng tiếp theo chứa thông tin của từng viên xúc xắc, mỗi dòng bao gồm một số \(s_i\) thể hiện số mặt của viên xúc xắc \(i\) và \(i\) số thể hiện linh vật trên con xúc xắc ấy.

Output

• Một số nguyên duy nhất là số tiền lớn nhất nhận được trong trường hợp may mắn nhất.

Sample

5 3
12 5 9 7 8
3 1 3 4
2 3 5
3 2 4 5

9

5 3
2 5 3 4 3
2 1 2
2 2 4
3 2 3 5 

15

Công đoạn làm bánh chưng bao gồm rất nhiều bước phức tạp, cầu kì, không chỉ đòi hỏi sự tỉ mỉ, cẩn thận từ người làm mà còn cần nhiều nguyên liệu sạch để tạo nên một chiếc bánh hoàn hảo cho dịp Tết.

Để đáp ứng cho nhu cầu bánh chưng ngày càng tăng, đặc biệt vào năm nay - Ất Tỵ 2025, nhà máy Đ quyết định sẽ dồn hết nguyên liệu và nhân công vào một đơn vị để dễ dàng quản lí và tăng năng suất. Nhà máy Đ có \(N\) đơn vị nằm trên một đường thẳng, mỗi đơn vị ở vị trí \(p_i\) trên đường thẳng đó và chi phí để chuyển hết nhân lực về đơn vị \(i\) là:

Với mỗi đơn vị \(i\), hãy tính chi phí để chuyển hết nhân lực từ các đơn vị khác về đơn vị \(i\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \le N \le 2 * 10^5)\).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(p_1, p_2, \ldots, p_N\) \((1 \le p_i \le 10^9)\).

Output

• Một dòng chứa \(N\) số lần lượt là chi phí khi chuyển tất cả nhân lực về đơn vị \(i\).

Scoring

• Subtask \(1\) \((40\%)\): \(1 \le N, p_i \le 10^2\).
• Subtask \(2\) \((30\%)\): \(1 \le N \le 2*10^5, 1 \le p_i \le 10^6\).
• Subtask \(3\) \((30\%)\): \(1 \le N \le 2*10^5, 1 \le p_i \le 10^9\).

Sample

4
1 2 2 5

6 4 4 10

4
5 3 1 6

7 7 11 9