Một mảng được gọi là "mảng gương" nếu đọc từ trái sang hay phải sang đều mang lại dãy số giống nhau (mảng đối xứng). Cho mảng A gồm N số nguyên dương. Bạn được phép thực hiện thao tác: Chọn 2 phần tử kề nhau và gộp chúng lại thành 1 phần tử có giá trị bằng tổng của chúng. Hãy tìm số thao tác ít nhất để biến A thành một mảng gương.

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^9).

Output: Số thao tác gộp ít nhất.

Ví dụ:

Input:

4
1 4 5 1

Output:

1

(Giải thích: Gộp 4 và 5 thành 9. Mảng trở thành 1 9 1 là mảng gương).

Trạm radar đặt tại tọa độ (0, 0) có bán kính phủ sóng là R. Bạn hãy tính xem có bao nhiêu điểm có tọa độ nguyên (cả hoành độ và tung độ đều là số nguyên) nằm hoàn toàn bên trong hoặc nằm ngay trên đường ranh giới của vùng phủ sóng radar này.

Input: Một dòng chứa số nguyên dương R (1 <= R <= 10^6).

Output: Số lượng điểm nguyên thỏa mãn.

Ví dụ:

Input:

2

Output:

13

(Giải thích: Các điểm là (0,0), (0,1), (0,2), (0,-1), (0,-2), (1,0), (2,0), (-1,0), (-2,0), (1,1), (1,-1), (-1,1), (-1,-1)).

Một mỏ quặng có N đống khoáng sản, đống thứ i có khối lượng Wi kg và chứa tổng giá trị là Vi đồng. Chiếc xe lùi của bạn chỉ chở được tối đa M kg. Rất may, bạn có thể xúc một phần lẻ của một đống quặng (ví dụ lấy 0.5 kg). Hãy tìm cách xúc quặng lên xe sao cho tổng giá trị thu được là lớn nhất.

Input:

Dòng 1: N, M (1 <= N <= 10^5, 1 <= M <= 10^9).

N dòng tiếp theo: Mỗi dòng 2 số nguyên Wi, Vi (1 <= Wi, Vi <= 10^5).

Output: Giá trị lớn nhất thu được, in ra phần nguyên (làm tròn xuống).

Ví dụ:

Input:

3 50
10 60
20 100
30 120

Output:

240

(Giải thích: Lấy toàn bộ đống 1 (10kg, 60đ), toàn bộ đống 2 (20kg, 100đ), và 20/30 đống 3 (20kg, 80đ). Tổng khối lượng 50kg, giá trị 240đ).

Kho hàng có N loại pin năng lượng. Loại pin thứ i có trọng lượng Wi, dung lượng điện Vi và bạn chỉ có số lượng tối đa là C_i viên pin loại này. Một robot thám hiểm cần nạp pin vào khoang chứa có tải trọng tối đa là M. Hãy tìm cách chọn các viên pin sao cho không vượt quá tải trọng M mà dung lượng điện nạp được là lớn nhất.

Input:

Dòng 1: N, M (1 <= N <= 100, 1 <= M <= 10^4).

N dòng tiếp theo: Mỗi dòng 3 số nguyên Wi, Vi, Ci (1 <= Wi, Vi <= 1000, 1 <= Ci <= 100).

Output: Tổng dung lượng điện lớn nhất.

Ví dụ:

Input:

2 10
3 4 2
4 5 3

Output:

13

(Giải thích: Chọn 2 viên loại 1 (nặng 6, điện 8) và 1 viên loại 2 (nặng 4, điện 5). Tổng nặng 10, điện 13).