Bài tập

Người anh tham lam đến đảo châu báu, trên đảo có \(N\) loại vàng, mỗi loại có số lượng không giới hạn. Một thỏi vàng loại \(i\) nặng \(w_i\) và có giá trị \(v_i\). Người anh mang theo một chiếc túi chịu được tổng trọng lượng tối đa \(M\).

Hãy tìm tổng giá trị lớn nhất có thể mang đi, biết rằng mỗi loại có thể lấy bao nhiêu thỏi tuỳ ý (kể cả không lấy) và tổng trọng lượng không vượt quá \(M\).

Input

• Dòng đầu chứa hai số nguyên \(M\) và \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(v_i\) và \(w_i\): giá trị và trọng lượng của một thỏi loại \(i\).

Output

In ra một số nguyên duy nhất: tổng giá trị lớn nhất.

Constraints

• \(1 \le N \le 500\)
• \(1 \le M \le 2 \cdot 10^6\)
• \(1 \le w_i \le 10^9\)
• \(0 \le v_i \le 10^9\)
• \(N \cdot \sum_{i=1}^{N} \max(0,\, M - w_i) \le 10^8\) (các loại nặng hơn \(M\) không đóng góp vào tổng này).

Sample Input

13 3
6 4
5 3
9 5

Sample Output

23

Explanation

Chọn \(2\) thỏi loại 3 (nặng \(10\), giá trị \(18\)) và \(1\) thỏi loại 2 (nặng \(3\), giá trị \(5\)): tổng nặng \(13\), giá trị \(23\). Đây là phương án tốt nhất.

Người anh tham lam đến đảo châu báu, trên đảo có \(N\) hòn vàng. Hòn vàng thứ \(i\) nặng \(w_i\) và có giá trị \(v_i\). Người anh mang theo một chiếc túi chịu được tổng trọng lượng tối đa \(M\), mỗi hòn vàng chỉ có thể lấy tối đa một lần.

Hãy tìm tổng giá trị lớn nhất của các hòn vàng mà người anh có thể bỏ vào túi mà tổng trọng lượng không vượt quá \(M\).

Input

• Dòng đầu chứa hai số nguyên \(M\) và \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(v_i\) và \(w_i\): giá trị và trọng lượng của hòn vàng thứ \(i\).

Output

In ra một số nguyên duy nhất: tổng giá trị lớn nhất.

Constraints

• \(1 \le N \le 500\)
• \(1 \le M \le 2 \cdot 10^6\)
• \(0 \le w_i \le 10^9\)
• \(0 \le v_i \le 10^9\)
• \(N \cdot \sum_{i=1}^{N} \max(0,\, M - w_i) \le 10^8\) (các hòn vàng nặng hơn \(M\) không đóng góp vào tổng này).

Sample Input

12 4
6 3
9 7
5 4
13 9

Sample Output

19

Explanation

Chọn hòn 2 và hòn 3 (nặng \(7+4=11 \le 12\)) được giá trị \(14\); chọn hòn 1 và hòn 4 (nặng \(3+9=12\)) được \(19\); chọn hòn 1, 2 (nặng \(10\)) được \(15\). Kết quả tốt nhất là \(19\).

Người anh tham lam đến đảo châu báu, trên đảo có \(N\) hòn vàng. Hòn vàng thứ \(i\) nặng \(w_i\) và có giá trị \(v_i\). Lần này người anh mang theo hai chiếc túi, chịu được trọng lượng tối đa lần lượt là \(M_1\) và \(M_2\). Mỗi hòn vàng chỉ được bỏ vào tối đa một túi (hoặc bỏ lại), và tổng trọng lượng trong mỗi túi không được vượt quá sức chịu của túi đó.

Hãy tìm tổng giá trị lớn nhất của các hòn vàng mang đi được.

Input

• Dòng đầu chứa ba số nguyên \(M_1\), \(M_2\) và \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(v_i\) và \(w_i\): giá trị và trọng lượng của hòn vàng thứ \(i\).

Output

In ra một số nguyên duy nhất: tổng giá trị lớn nhất.

Constraints

• \(1 \le N \le 200\)
• \(1 \le M_1, M_2 \le 200\)
• \(0 \le w_i \le 200\)
• \(0 \le v_i \le 200\)

Sample Input 1

9 5 4
10 5
7 4
8 6
3 3

Sample Output 1

21

Sample Input 2

6 6 3
9 4
8 4
5 4

Sample Output 2

17

Explanation

Ví dụ 1: đặt hòn 3 và hòn 4 vào túi 1 (nặng \(6+3=9\), giá trị \(11\)) và hòn 1 vào túi 2 (nặng \(5\), giá trị \(10\)): tổng \(21\). Cách khác, hòn 1 và 2 vào túi 1 và hòn 4 vào túi 2, chỉ được \(20\). Ví dụ 2: mỗi túi chứa được đúng một hòn nặng \(4\) nên chọn hai hòn giá trị \(9\) và \(8\), tổng \(17\).

Cho ba số nguyên khác \(0\) là \(m, n, k\). Với mỗi số theo đúng thứ tự đã cho, hãy biến đổi như sau: nếu số đó âm thì thay bằng bình phương của nó, nếu số đó dương thì thay bằng lập phương của nó.

Input

Một dòng gồm ba số nguyên \(m, n, k\).

Output

Ba giá trị sau biến đổi, theo thứ tự tương ứng, cách nhau bởi một dấu cách.

Constraints

• \(1 \le |m|, |n|, |k| \le 1000\)

Sample Input

-4 5 -1

Sample Output

16 125 1