Chi Chi Chành Chành (Tháng Bảy Version)


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 500M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

"Chi chi chành chành

Cái đanh thổi lửa

Con ngựa đứt cương

Ba vương ngũ đế

Bắt dế đi tìm

Ù à ù ập"

Đây là dị bản được nhân dân biến đổi lại so với bản gốc.

Xưa kia, có nhà phú hộ làm nghề rèn giàu khắp một vùng. Họ truyền cái nghề này đã qua bao đời. Đến đời ông X, thì càng phất hơn. Gia nhân trong nhà vào ra suốt ngày đêm không ngưng nghỉ. Với việc sống trong nhung lụa từ nhỏ, ông X đã từ lâu chẳng xem những người dưới mình ra gì. Ông chỉ biết quát nạn, mắng nhiếc họ. Người làm đông là thế, nhưng tuyệt nhiên, chẳng ai biết, vì sao cái lò rèn nhà ông lại được lòng các quan đến vậy. Chỉ có người trong nhà luôn truyền tai nhau về lời nhắc của một lão phù thủy đã giúp ông có được cơ ngơi đó: "Một khi ba vương liên tiếp ra đời, ngũ đế chết yểu, thì oán linh giữ của quay lại trả thù."

Nhà giàu có, lại có tính ham mê sắc lạ, ông đã cưới tới 4 đời vợ, có 5 mống con. Nhưng với bản tính trăng hoa có sẵn, trong một lần đi xem hát, ông đã bị cuốn hút bởi một ả đào. Ông bèn kết duyên và dắt ả về làm thiếp. Nhưng người đàn bà này lại khác xa với 4 bà trước, cô ta làm nghề hát, còn những người kia đều là con nhà quyền quý. Khi biết được ả đào mang theo 3 giọt máu nhà ông X, ả được ông cưng sủng, khiến cho 4 bà vợ đầu nảy sinh căm tức trong lòng. Bốn bà đều nhớ lại lời sấm của thầy phù thủy năm xưa, nghĩ rằng 3 đứa con của ả đào sinh ra là lúc 5 đứa con của các ả không thể sống tiếp. Sự lo lắng kết hợp với lòng ghen tuông đã đẩy cả bốn vào đầy rẫy những tội ác.

Trong một lần ông X xem bói, thầy bói phán rằng nhà họ đang có 3 mầm quỷ. Quá trùng hợp, ông X sinh nghi, và dần xa lánh ả đào mới cưới. Bốn bà sau khi biết tin thì thầm vui sướng, vì chính họ là người đã sai ông thầy nói những điều đó. Ông X đã tìm cách cho ả đào dùng thuốc để phá đi 3 mầm sống mới. Với sự tức tưởi và thương con, ả ta cũng tự vẫn mà đi theo. Và từ đây, mọi chuyện bắt đầu.

Ông X vốn tính rượu chè, đam mê cờ bạc. Và một trong số những trò chơi đốt tiền của ông là cược chọi dế. Sắp tới, trong vùng có một giải chọi dế lớn, tổ chức trong \(N\) vòng. Ông X đã sắp xếp một lượng lớn đồng vàng để dùng vào giải cược này. Vòng thứ \(i\), ông dự định cược \(a_i\) đồng vàng. Theo kế hoạch của mình, ông sẽ chỉ cược vào một vài vòng chắc chắn. Tuy nhiên, bọn đầu têu giải đã yêu cầu những người cược phải đặt cược liên tục từ vòng đầu, nếu dừng ở vòng nào thì coi như không được tiếp tục cược ở những vòng kế tiếp. Ông X lúc này hoàn toàn điêu đứng, ông không thể đào thêm vàng để cược, nhưng rồi ông bình tĩnh lại và quyết định thay đổi không quá \(K\) lần. Mỗi lần, ông có thể chuyển một đồng vàng từ vòng này sang một vòng khác. Ông cũng chỉ được thay đổi trước khi giải đấu bắt đầu, vì vậy ông đã chọn cách thay đổi tối ưu nhất.

Vào đêm trăng tròn tháng đó, đó là vòng cuối cùng mà ông X có thể đặt cược, ông ta thua, và mất trắng toàn bộ số vàng cược. Quá cay cú, sau khi về nhà, ông đã chửi rủa, hành hạ người làm. Và một trong số họ vì quá uất ức và không thể kìm chế được, đã vùng lên, ném một thứ gì đó vào lò rèn. Cả lò rèn nổ tung. Đàn ngựa gần đó bị sắt nóng trúng người thì phát điên lên, chạy khỏi chuồng, văng đứt dây cương rồi giẫm đạp lên nhau, lên cả những người đứng gần đó đang chạy toán loạn, và cả 5 đứa con với 4 bà vợ đầu và chính ông.

Chỉ sau một đêm, nhà phú hộ X tuyệt tử tuyệt tôn.

Sự thật sau đó được làm sáng tỏ, ông X đã sử dụng các loại tà thuật, sử dụng các oán linh để giữ của, và lời nhắc của lão phù thủy không phải là lời dặn, mà chính là lời tiên tri của nhà ông X. Đó là hệ quả cho việc sử dụng các thuật chú cổ xưa.

Hãy cho biết, ông X chơi được tới vòng thứ mấy.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên \(N, K \ (1\le N \le 10^6; 0\le K \le \sum_{a_i})\);
  • Dòng tiếp theo chứa \(N\) số nguyên \(a_i \ (0\le a_i \le 10^6)\).

Kết quả

  • Kết quả bài toán.

Chấm điểm

  • Subtask 1 (10%): \(K=0\).
  • Subtask 2 (50%): \(N \le 10^3\).
  • Subtask 3 (40%): Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

6 1
2 0 1 0 2 0

output

3

Comments

There are no comments at the moment.