Bài tập

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

Thầy Phú xếp \(N\) học sinh thành một hàng để phát kẹo. Bạn đầu hàng nhận \(1\) viên, các bạn tiếp theo lần lượt nhận nhiều hơn bạn ngay trước đúng \(3\) viên (dãy \(1, 4, 7, 10, \dots\)). Thầy phát lần lượt từ đầu hàng và chỉ phát khi số kẹo còn lại đủ cho bạn đó theo đúng quy tắc; ngay khi không đủ, thầy dừng lại (không phát thêm cho ai nữa, số kẹo dư thầy đem về).

Thầy chỉ có \(K\) viên kẹo. Hãy tính số học sinh nhận được kẹo.

Input

• Một dòng gồm hai số nguyên dương \(N\) và \(K\).

Output

• In ra một số nguyên là số học sinh nhận được kẹo.

Constraints

• \(1 \le N \le 10^{5}\).
• \(1 \le K \le 10^{15}\).

Sample Input 1

5 30

Sample Output 1

4

Sample Input 2

4 100

Sample Output 2

4

Explanation

Ở ví dụ 1, bốn bạn đầu cần \(1+4+7+10 = 22 \le 30\) viên, bạn thứ năm cần thêm \(13\) viên nên \(35 > 30\): dừng lại. Ở ví dụ 2, kẹo còn dư nhưng lớp chỉ có \(4\) bạn.

Sắn và Mì chơi một trò với \(N\) quân bài, quân bài thứ \(i\) ghi số \(S_i\). Các lượt bốc diễn ra như sau: Sắn bốc \(1\) quân, sau đó Mì bốc \(2\) quân, rồi Sắn bốc \(2\) quân, rồi Mì bốc \(2\) quân, và cứ thế luân phiên (mỗi lần trừ lần đầu là \(2\) quân) cho đến khi hết bài. Ở mỗi lượt, người chơi được tự chọn quân bài bất kỳ còn trên bàn; nếu còn ít quân hơn số cần bốc thì bốc hết số còn lại. Cả hai đều chơi tối ưu để tổng số trên các quân mình bốc được là lớn nhất.

Người có tổng lớn hơn thắng. Hãy cho biết kết quả của Sắn: THANG nếu Sắn thắng, HOA nếu hai tổng bằng nhau, THUA nếu Sắn thua.

Input

• Dòng đầu: số nguyên \(N\).
• Dòng sau: \(N\) số nguyên \(S_1, \dots, S_N\).

Output

Một dòng duy nhất: THANG, HOA hoặc THUA.

Constraints

• \(1 \le N \le 10^6\)
• \(0 \le S_i \le 10^9\)

Sample Input

4
8 3 9 5

Sample Output

THUA

Explanation

Sắn bốc \(9\); Mì bốc \(8\) và \(5\) được \(13\); Sắn bốc nốt \(3\) được \(12\). Vì \(12 < 13\) nên Sắn thua.