Có \(n\) miếng sushi. Mỗi miếng có hai tham số: "loại topping" \(t_i\) và "độ ngon" \(d_i\) . Bạn sẽ chọn \(k\) trong số các miếng sushi này để ăn. Độ hài lòng là tổng của "độ ngon cơ bản" và "thưởng đa dạng", và sẽ được tính như sau:

• Độ ngon cơ bản là tổng độ ngon của các miếng sushi bạn ăn.
• Thưởng đa dạng là \(x\times x\), trong đó \(x\) là số loại topping khác nhau của các miếng sushi bạn ăn.

Bạn muốn có độ hài lòng cao nhất có thể. Hãy tìm độ hài lòng tối đa này.

INPUT FORMAT

Dòng đầu tiên gồm hai số nguyên dương \(n, k(1 \leq k \leq n \leq 10^5)\).

\(n\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên dương \(t_i\) và ~d_i(1 \leq t_i \leq n, 1 \leq d_i \leq 10^9).

OUTPUT FORMAT

In ra độ hài lòng cao nhất có thể đạt được.

Ví dụ 1:

Input

5 3
1 9
1 7
2 6
2 5
3 1

Output

26

Ví dụ 2:

Input

7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5

Output

25

Giải thích ví dụ mẫu

Ví dụ 1:

• Input: 5 3
• Giải thích: Chọn 3 miếng sushi với các loại topping khác nhau để đạt tổng độ ngon là 26.

Ví dụ 2:

• Input: 7 4
• Giải thích: Chọn 4 miếng sushi với nhiều loại topping khác nhau để có tổng độ hài lòng cao nhất là 25.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House