Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CATGO - Cắt gỗ

Ở một xưởng gỗ có rất nhiều đoạn gỗ thừa. Để đạt năng suất cao, người ta muốn tận dụng những thanh gỗ này. Tất nhiên giá trị của mỗi đoạn gỗ sẽ phụ thuộc vào độ dài của chúng. Tuy nhiên sự phụ thuộc này không đơn giản chỉ là sự phụ thuộc tuyến tính: các thanh gỗ càng dài càng có giá trị cao. Do đó, nếu cần thiết, người ta sẽ cắt các thanh gỗ này ra làm nhiều đoạn nhỏ hơn.

Người ta có một máy cắt, mỗi lần có thể cắt một thanh gỗ ra làm hai thanh có độ dài ngắn hơn. Do lưỡi cưa sẽ mòn dần trong quá trình cắt, chi phí của mỗi lần cắt sẽ được tính như sau: lần đầu sẽ mất 1VNĐ, lần thứ 2 sẽ là 2VNĐ, lần thứ 3 sẽ là 3VNĐ,...

Nhiệm vụ của bạn sẽ là tính lợi nhuận lớn nhất có thể thu được từ các đoạn gỗ thừa này.

Dữ liệu

  • Dòng đầu ghi số N, số thanh gỗ thừa.
  • N dòng sau, mỗi dòng ghi một số nguyên dương là độ dài của một thanh gỗ.
  • Dòng tiếp theo ghi số M, số độ dài có giá trị.
  • M dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương lần lượt là độ dài của một đoạn gỗ và giá trị thu được (tính bằng VNĐ) nếu ta có đoạn gỗ đó.

Kết quả

Ghi ra một số duy nhất là lợi nhuận lớn nhất có được, đừng quên tính cả chi phí dùng để cắt gỗ.

Giới hạn

  • 1 ≤ N ≤ 50.
  • 1 ≤ M ≤ 50.
  • Độ dài của một thanh gỗ không quá 50.
  • Giá trị thu được của một đoạn gỗ không quá 50.

Ví dụ

Dữ liệu
2
3
4
2
1 10
2 11

Kết quả
55

Được gửi lên bởi:VOJ problem setters
Ngày:2008-06-07
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:VNOI Marathon '08 - Practice Round
Problem Setter: Khúc Anh Tuấn

hide comments
2020-08-15 11:47:04
One hit AC
2016-09-30 09:06:57
Code:
http://shink.in/43dk6
2016-09-26 10:05:08
trâu cũng AC :)))
2015-08-18 15:44:21
mất cả ngày, cuối cùng cũng
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.