[DMH_HSG_VP_24] Tặng hoa

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python

Bờm muốn mua một bó hoa gồm ~n~ bông hoa để tặng bạn nhân ngày Quốc tế Phụ nữ. Tại cửa hàng hoa, Bờm phát hiện được:

  • Cửa hàng có ~m~ loại hoa, đánh số ~1..m~, mỗi loại hoa đều có ít nhất ~n~ bông;
  • Với loại hoa ~i~, bông đầu tiên có trong bó hoa sẽ cung cấp điểm thẩm mĩ ~a_i~, mỗi bông tiếp theo cung cấp điểm thẩm mĩ ~b_i~, nghĩa là nếu Bờm mua ~x_i~ ~(x_i > 0)~ bông hoa loại ~i~, điểm thẩm mĩ loại hoa này đóng góp cho bó hoa sẽ là ~a_i + (x_i - 1) \times b_i~.

Yêu cầu

Hãy viết chương trình xác định tổng điểm thẩm mĩ lớn nhất của bó hoa Bờm có thể mua được.

Dữ liệu đầu vào

Gồm ~m + 1~ dòng:

  • Dòng 1: hai số nguyên ~n,\ m~ ~(1 \le n \le 10^9;\ 1 \le m \le 10^5)~;
  • Dòng ~2..m + 1~: dòng ~i + 1~ ghi hai số nguyên ~a_i,\ b_i~ ~(0 \le a_i, b_i \le 10^9)~.

Dữ liệu đầu ra

Gồm số nguyên là điểm thẩm mĩ lớn nhất một bó hoa gồm ~n~ bông hoa có thể đạt được.

Ràng buộc dữ liệu

  • 8% điểm: ~n, m \le 7~ và ~a_i \ge b_i\ \forall\ i = 1..m~;
  • 12% điểm khác: ~n, m \le 7~;
  • 12% điểm khác: ~n, m \le 1000~ và ~a_i \ge b_i\ \forall\ i = 1..m~;
  • 28% điểm khác: ~n, m \le 1000~;
  • 32% điểm khác: ~a_i \ge b_i\ \forall\ i = 1..m~;
  • 8% điểm còn lại: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1
INPUT
4 3
5 0
1 4
2 2
OUTPUT
14

Giải thích: Bó hoa tối ưu gồm ~1~ bông hoa loại ~1~ và ~3~ bông hoa loại ~2~. Tổng điểm: ~5 + 1 + 4 + 4 = 14~.

Ví dụ 2
INPUT
5 3
5 2
4 2
3 1
OUTPUT
16

Giải thích: Bó hoa tối ưu gồm ~2~ bông hoa loại ~1~ và ~2~ bông hoa loại ~2~ và ~1~ bông hoa loại ~3~. Tổng điểm: ~5 + 2 + 4 + 2 + 3 = 16~.

Bình luận

Hãy đọc nội quy trước khi bình luận.