Happy New Year 2025

Nhập xâu \(S\). Đếm số từ trong xâu \(S\).

Input

• Nhập xâu \(S\) (tổng số ký tự không vượt quá \(10^5\)).

Output

• In ra số lượng từ trong xâu \(S\).

Example

code dream

2

Vào dịp Tết Nguyên Đán, làng LQDOJ tổ chức cuộc thi gói bánh chưng truyền thống hàng năm. Trong kho của làng chỉ có đúng \(M\) nắm gạo nếp, được chuẩn bị kỹ lưỡng để chia cho những người tham gia gói bánh.

Mỗi gia đình sẽ lần lượt tham gia từ gia đình thứ \(1\), gia đình thứ \(2\), và lần lượt cho đến hết. Khi tham gia mỗi gia đình sẽ cần một số lượng gạo khác nhau tùy vào kế hoạch gói bánh của họ. Cụ thể, gia đình thứ \(i\) cần \(a_i\) nắm gạo nếp có thể gói bánh chưng. Mỗi gia đình chỉ được phép gói bánh nếu họ nhận đủ số nắm gạo mà họ cần.

Yêu cầu: Bạn hãy xác định xem có bao nhiêu gia đình có thể nhận đủ số nắm gạo để có thể gói bánh chưng theo trước khi gạo nếp cạn kiệt. Biết rằng nếu số gạo còn lại không đủ cho một gia đình, họ sẽ nhận số gạo còn lại nhưng không thể gói thành bánh chưng.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((1 \le N\le 10^5,1 \le M \le 10^8)\).
• Dòng tiếp theo chứa \(N\) số nguyên dương cách nhau một khoảng trắng lần lượt là \(a_1,a_2,...,a_N\) \((1 \le a_i \le 10^5).\)

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Example

5 10
2 5 2 3 3

3

Một dãy gồm \(n\) số nguyên không âm \(a_1, a_2,..., a_n\) được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả \((n­-1)\) khoảng trắng. Người ta muốn đặt \(k\) dấu cộng và (\(n-1-k\)) dấu trừ vào \((n­-1)\) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất.

Ví dụ, với dãy gồm \(5\) số nguyên \(28, 9, 5, 1, 69\) và \(k = 2\) thì cách đặt \(28+9-5-1+69\) là biểu thức có giá trị lớn nhất.

Yêu cầu: Cho dãy gồm \(n\) số nguyên không âm \(a_1, a_2,..., a_n\) và số nguyên dương \(k\), hãy tìm cách đặt \(k\) dấu cộng và (\(n-1-k\)) dấu trừ vào (\(n­-1\)) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(n, k\) (\(k < n\));
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2,..., a_n\) (a_n ≤ 10^6)

Output

• Một số nguyên là giá trị của biểu thức đạt được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n ≤ 10^5\) và \(k = 1\);
• Subtask \(2\) (\(50\%\) số điểm): \(n ≤ 10^5\);

Example

5 2
28 9 5 1 69 

100

Siêu thị khuyến mãi
Giá một hộp sữa Vinamilk là 5000 đồng. Nhân dịp khai trương, siêu thị ABC có chương trình khuyến mãi sữa Vinamilk như sau: mua \(x\) hộp sữa Vinamilk sẽ được tặng thêm \(y\) hộp sữa Vinamilk.

Khang đến siêu thị ABC mua \(a\) hộp sữa Vinamilk. Hỏi số tiền ít nhất Khang phải trả để mua được tối thiểu \(a\) hộp sữa Vinamilk?

Input

• Một dòng gồm \(3\) số nguyên dương \(x, y, a\).
• Giới hạn:
  • \(1 \le x, y \le 1000\)
  • \(1 \le a \le 10^{15}\)

Output

• Số tiền ít nhất Khang phải trả (đơn vị nghìn đồng).

Example

2 2 5

15

1 1 9

25