Có n con quái xuất hiện trong thành phố. Để tiêu diệt được một con quái cần tốn a[i] viên đạn đối với con quái thứ i. Nếu bạn tiêu diệt hai con quái gần nhau, ví dụ con quái thứ i và i + 1 thì chỉ cần 2 x a[i] viên đạn.

Nhiệm vụ của bạn là làm sao tốn tổng số đạn ít nhất để tiêu diệt hết đám quái và bảo vệ thành phố.

Đầu vào

• Dòng đầu tiên gồm số nguyên n (2≤n≤10^6 ), số lượng quái vật trong thành phố.

• n số nguyên dương a[i] (1≤a[i]≤10^9 ), cách nhau bởi dấu cách, số đạn để tiêu diệt quái vật thứ i.

Giới hạn

N/A

Đầu ra

In ra tổng số đạn tối thiểu để tiêu diệt hết quái vật.

Ví dụ :

Input 01

5
1 3 2 5 4

Output 01

10

Trong cửa hàng có n viên kẹo, viên kẹo thứ i có giá tiền là p[i] và độ ngọt là h[i]. Bạn có tối đa m tiền trong túi, hãy dùng số tiền đó một cách khéo léo để mua kẹo trong cửa hàng, sao cho tổng độ ngọt của tất cả viên kẹo bạn mua là lớn nhất có thể.

Đầu vào

• Dòng đầu tiên gồm hai số nguyên dương n, m (1≤n≤100,1≤m≤10^6 ), số viên kẹo có trong của hàng.

• n số nguyên dương p[i] (1≤i≤n,p[i]≤10^6 ), giá tiền của viên kẹo thứ i.

• n số nguyên dương h[i] (1≤h[i]≤10^9 ), độ ngọt của viên kẹo thứ i.

Giới hạn

N/A

Đầu ra

• In ra một kết quả bài toán.

Ví dụ :

Input 01

5 4
6 2 3 5 1
3 2 4 2 1

Output 01

5

Ở thành phố nơi bạn sống vừa mới khai trương một rạp chiếu phim lớn. Hôm nay, rạp sẽ chiếu n bộ phim theo khung giờ cố định, bộ phim thứ i sẽ chiếu vào khung giờ t[i-1] đến t[i]. Trước khi xem bất kỳ bộ phim nào, bạn phải mua vé xem bộ phim ấy, có hai loại vé cho bạn lựa chọn:

• Vé loại 1: Vé xem phim với giá p[i] tương ứng cho bộ phim thứ i.

• Vé loại 2: Vé đặc biệt có thể xem nhiều bộ phim với tổng thời lượng tối đa 180 phút với giá 100 đô.

Nhiệm vụ của bạn là tính số tiền tối ưu nhất phải trả cho mỗi lần mua vé phim.

Ví dụ , rạp chiếu 3 bộ phim với các khung giờ t=[0,10,20,30], giá vé của các bộ phim là p=[40,50,60]. Bộ phim thứ nhất và thứ hai bạn dùng vé loại 1 là tối ưu nhất, số tiền bạn phải trả là 40,50. Bộ phim thứ ba bạn dùng vé loại hai là tối ưu nhất, vì trước đó bạn đã trả 40 + 50 = 90 rồi, nên bạn chỉ cần trả thêm 10 đô nữa là có vé loại 2 với thời lượng 180 phút, thời lượng này lớn hơn thời lượng của những bộ phim gần nhất nên vé này hợp lệ.

Đầu vào

• Dòng đầu tiên chứ số nguyên dương n (1≤n≤10^5), số lượng phim rạp sẽ chiếu.

• n số nguyên t[i] (0≤i≤n, 1≤t[i]≤1000), thời lượng của các bộ phim, mặc định bộ phim đầu tiên bắt đầu vào thời điểm t[0] = 0, đảm bảo các t[i] là duy nhất và được sắp xếp tăng dần.

• n số nguyên p[i] (1≤i≤n, 1≤p_i≤99), giá vé của bộ phim thứ i.

Giới hạn

N/A

Đầu ra

• In ra n số nguyên cách nhau bởi dấu cách là số tiền tối ưu nhất sẽ chi trả khi xem tới bộ phim thứ i(1≤i≤n).

Ví dụ :

Input 01

3
10 20 30
40 50 60

Output 01

40 50 10

Bạn được cho n hòn đá, mỗi hòn đá có cân nặng là a[i].

Bạn phải chất các hòn đá thành từng đống liên tiếp nhau và giữ đúng thứ tự các đống so với dãy hòn đá ban đầu.

Mỗi hòn đá ban đầu được coi là một đống, khi bạn chất hai đống liên tiếp i và i+1 thì sẽ tốn chi phí bằng tổng cân nặng của hai đống đá đó và đống đá mới vừa chất sẽ có cân nặng là a[i] + a[i + 1].

Nhiệm vụ của bạn là chất tất cả các hòn đá này thành một đống đá với chi phí nhỏ nhất có thể.

Đầu vào

• Dòng đầu tiên gồm số nguyên dương n (1≤n≤100), số lượng hòn đá ban đầu.

• Dòng tiếp theo gồm n số nguyên dương a_i (1≤a[i]≤10^9 ), cách nhau bởi dấu cách, cân nặng của từng hòn đá.

Giới hạn

N/A

Đầu ra

In ra một số nguyên duy nhất là đáp án của bài toán.

Ví dụ :

Input 01

4
6 8 1 9

Output 01

48

Giải thích :

(6, 8, 1, 9) -> (6, 9, 9) -> (15, 9) -> (24)

=> Chi phí: 9+15+24=48.