{"code":"abc149e","name":"AtCoder Beginner Contest 149 - E - Handshake","description":"Takahashi tới một buổi tiệc với tư cách là vị khách đặc biệt. Có $N$ vị khách bình thường khác nhau ở buổi tiệc, với vị khách thứ $i$ có sức mạnh là $A_i$.\r\n\r\nTakahashi quyết định bắt tay $M$ lần để tăng sự **vui vẻ** của buổi tiệc (cứ coi như bây giờ độ vui vẻ bằng $0$). Một lần bắt tay sẽ được thực hiện như sau:\r\n - Takahashi chọn một vị khách $x$ để bắt tay trái, và một vị khách $y$ để bắt tay phải ($x$ và $y$ có thể giống nhau)\r\n - Sau đó, anh ta bắt cả hai tay với hai vị khách $x$ và $y$ để tăng độ vui vẻ lên $A_x + A_y$.\r\n\r\nTuy nhiên, Takahashi không thể thực hiện phép bắt tay giống hệt quá một lần. Cụ thể hơn, điều kiện sau cần được thỏa mãn:\r\n - Giả sử ở lần bắt tay thứ $k$, Takahashi bắt tay với vị khách $x_k$ và $y_k$. Khi đó, không tồn tại cặp $(p, q)$ $(1 \\leq p < q \\leq M$ sao cho $(x_p, y_p) = (x_q, y_q)$.\r\n\r\nHỏi, độ vui vẻ lớn nhất có thể đạt được sau $M$ cú bắt tay là bao nhiêu?\r\n\r\n#### Giới hạn\r\n - $1 \\leq N \\leq 10^5$\r\n - $1 \\leq M \\leq N^2$\r\n - $1 \\leq A_i \\leq 10^5$\r\n - Tất cả các giá trị đều là số nguyên.\r\n \r\n#### Định dạng đầu vào\r\n\r\n> $N$ $M$\r\n> $A_1$ $A_2$ $\\dots$ $A_N$\r\n\r\n#### Định dạng đầu ra\r\nIn ra độ vui vẻ lớn nhất có thể đạt được sau $M$ lần bắt tay\r\n\r\n#### Ví dụ\r\n!!! question \"Ví dụ 1\"\r\n    ???+ \"Đầu vào\"\r\n        ```sample\r\n        5 3\r\n        10 14 19 34 33\r\n        ```\r\n    ???+ success \"Đầu ra\"\r\n        ```sample\r\n        202\r\n        ```\r\n    ??? warning \"Giải thích\"\r\n        Takahashi sẽ thực hiện những cú bắt tay sau:\r\n        - Cú bắt tay đầu tiên bắt tay với vị khách thứ $4$ và $4$\r\n        - Cú bắt tay tiếp theo bắt tay với vị khách $4$ và $5$\r\n        - Cú bắt tay cuối cùng bắt tay với vị khách $5$ và $4$\r\n        \r\n!!! question \"Ví dụ 2\"\r\n    ???+ \"Đầu vào\"\r\n        ```sample\r\n        9 14\r\n        1 3 5 110 24 21 34 5 3\r\n        ```\r\n    ???+ success \"Đầu ra\"\r\n        ```sample\r\n        1837\r\n        ```\r\n        \r\n!!! question \"Ví dụ 2\"\r\n    ???+ \"Đầu vào\"\r\n        ```sample\r\n        9 73\r\n        67597 52981 5828 66249 75177 64141 40773 79105 16076\r\n        ```\r\n    ???+ success \"Đầu ra\"\r\n        ```sample\r\n        8128170\r\n        ```","points":1.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}