Dragons

Nguồn: http://codeforces.com

Kirito is stuck on a level of the MMORPG he is playing now. To move on in the game, he's got to defeat all n dragons that live on this level. Kirito and the dragons have strength, which is represented by an integer. In the duel between two opponents the duel's outcome is determined by their strength. Initially, Kirito's strength equals s.

If Kirito starts duelling with the i-th (1 ≤ i ≤ n) dragon and Kirito's strength is not greater than the dragon's strength x_i, then Kirito loses the duel and dies. But if Kirito's strength is greater than the dragon's strength, then he defeats the dragon and gets a bonus strength increase by y_i.

Kirito can fight the dragons in any order. Determine whether he can move on to the next level of the game, that is, defeat all dragons without a single loss.

Input

The first line contains two space-separated integers s and n (1 ≤ s ≤ 10⁴, 1 ≤ n ≤ 10³). Then n lines follow: the i-th line contains space-separated integers x_i and y_i (1 ≤ x_i ≤ 10⁴, 0 ≤ y_i ≤ 10⁴) — the i-th dragon's strength and the bonus for defeating it.

Output

On a single line print "YES" (without the quotes), if Kirito can move on to the next level and print "NO" (without the quotes), if he can't.

Examples

input

2 2
1 99
100 0

output

YES

input

10 1
100 100

output

NO

Note

In the first sample Kirito's strength initially equals 2. As the first dragon's strength is less than 2, Kirito can fight it and defeat it. After that he gets the bonus and his strength increases to 2 + 99 = 101. Now he can defeat the second dragon and move on to the next level.

In the second sample Kirito's strength is too small to defeat the only dragon and win.

Tóm tắt đề:

_ Để thắng được vòng tiếp theo, Kirito cần hạ được n con rồng. Ban đầu, Kirito có chỉ số sức mạnh là s.

_ Nếu sức mạnh hiện tại của Kirito mạnh hơn sức mạnh x[i] của con rồng, thì Kirito sẽ đánh bại được con rồng và tăng thêm được 1 lượng sức mạnh là y[i]. Ngược lại, Kirito sẽ chết.

_ Hỏi : Kirito có đến được vòng tiếp theo hay không ?

Solution by ĐNK

Taxi

Nguồn:http:/codeforces.com

After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of s_i friends (1 ≤ s_i ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

Input

The first line contains integer n (1 ≤ n ≤ 10⁵) — the number of groups of schoolchildren. The second line contains a sequence of integers s₁, s₂, ..., s_n (1 ≤ s_i ≤ 4). The integers are separated by a space, s_i is the number of children in the i-th group.

Output

Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.

Examples

input

5
1 2 4 3 3

output

4

input

8
2 3 4 4 2 1 3 1

output

5

Note

In the first test we can sort the children into four cars like this:

·         the third group (consisting of four children),

·         the fourth group (consisting of three children),

·         the fifth group (consisting of three children),

·         the first and the second group (consisting of one and two children, correspondingly).

There are other ways to sort the groups into four cars.

Tóm tắt đề:

_ Có n nhóm học sinh. Nhóm thứ i chứa s[i] học sinh

_ Một chiếc taxi chỉ có tối đa 4 chỗ ngồi.

_ Các học sinh trong cùng 1 nhóm thì lại muốn ngồi chung trong 1 chiếc taxi. Và 1 chiếc taxi có thể chứa nhiều hơn 1 nhóm học sinh.

_ Hỏi : Cần ít nhất bao nhiêu chiếc taxi để chở hết toàn bộ n nhóm học sinh này.

Solution by ĐNK

Akhil And Colored Balls

Nguồn: https://www.codechef.com/

Akhil có rất nhiều quả bóng trắng và đen. Một ngày, anh chơi với chúng. Trong khi chơi, anh ta xếp các quả bảnh thành hai hàng, mỗi hàng chứa N quả banh. Hai hàng banh này được cung cấp cho bạn dưới dạng 2 chuỗi X, Y. Cả 2 chuỗi này chỉ chứa 'W' và 'B' trong đó 'B' ký hiệu cho qua banh màu trắng và 'B' ký hiệu cho quả banh màu đen.

Ngoài hai hàng banh này, Akhil có số lượng vô hạn các quả banh của mỗi màu. Anh ta muốn tạo ra một dòng nữa gồm N quả banh, ký hiệu bằng Z, sao cho tổng khoảng cách hamming giữa X và Z và khoảng cách hamming giữa Y và Z là tối đa.

Khoảng cách hamming giữa hai chuỗi X và Y được đỉnh nghĩa là số lượng vị trí mà màu của trái banh trong X khác với hàng Y ở tại vị trí đó. Ví dụ, khoảng cách hamming giữa “WBB” và “BWB” là 2, vì ở ví trí 1 và 2, màu tương ứng trong hai chuỗi khác nhau.

Vì có thể có nhiều cách tạo hàng Z, Akhil muốn bạn tìm chuỗi có thứ tự từ điển nhỏ nhất mà có giá trị như nói ở trên là lớn nhất.

Dữ liệu vào

·    Dòng đầu tiên của tập tin dữ liệu vào chứa một số nguyen T là số lượng bô test. Mô tả của T bộ test như sau:

·    Dòng đầu tiên của mỗi bộ test sẽ chứa một chuỗi X là cách sắp xếp các quả banh trong hàng đầu tiên.

·    Dòng thứ hai chứa một chuỗi Y là cách sắp xếp các quả banh trong hàng thứ hai.

Dữ liệu ra

·    Với mỗi bộ test, xuất ra một dòng duy nhất chứa chuỗi có độ dài là N là cách sắp xếp các quả banh trong hàng Z.

Ràng buộc

•   1 ≤ T ≤ 3

Giới hạn

·    Subtask #1 (10 điểm) : 1 ≤ N ≤ 16

·    Subtask #2 (20 điểm) : 1 ≤ N ≤ 10³

·    Subtask #3 (70 điểm) : 1 ≤ N ≤ 10⁵

Ví dụ

Input:

1

WBWB

WBBB

Output:

BWBW

Giải thích

Ví dụ 1. Như đã biết, khoảng các Hamming(WBWB, BWBW) và khoảng cách Hamming(WBBB, BWBW) = 4 + 3 = 7.

Bạn có thể thử những ía trị khác cho chuỗi Z, giá trị sẽ không bao giờ vượt quá 6

Lumpy – The Bus Driver

Nguồn: https://www.codechef.com/           

Lumpy là một tài xế xe buýt. Hôm nay, tên lơ xe nghỉ vì vậy Lumpy phải phụ trách luôn công việc của hắn ta. Trên xe buýt có N người. Đôi lúc sẽ có một số người không mang theo tiền thối và không thể trả vừa đúng giá trị của vé xe. Mỗi người trên xe buýt hôm nay vừa phải trả một số tiền lớn hơn giá trị thật sự của vé xe. Bạn được cho biết trước thông tin về số tiền trả thêm của mỗi người thông qua một mảng A có kích thước là N, trong đó A_i là số tiền (số lượng rupee, trong đó rupee là đơn vị tiền tệ của Ấn Độ) mà người thứ i phải trả thêm.

Sau khi kết thúc hành trình, Lumpy để ý rằng anh ta có P đồng mệnh giá một rupee và Q đồng mệnh giá hai rupee. Anh ta muốn thối lại những hành khách của anh ta bằng số tiền này. Vì là một người tốt bụng, Lumpy muốn thối lại đủ tiền cho càng nhiều người càng tốt. Lưu ý rằng Lumpy sẽ không thối lại tiền cho người thứ i nếu anh ta không thể trả đúng số tiền dư với những đồng xu anh ta có.

Lumpy đang bận lái xe buýt và cũng một phần không muốn tính số lượng người tối đa mà anh ta có thể làm hài lòng - Anh ta sẽ gây ra tai nạn nếu anh ta thử làm như vậy. Bạn có thể giúp anh ta với bài toán này?

Dữ liệu vào:

·       Dòng đầu tiên của dữ liệu vào chứa số nguyên T là số lượng bộ test. Mô tả của T bộ test như sau.

·       Với mỗi bộ test, dòng đầu tiên chứa ba số nguyên cách nhau bởi khoảng trắng N, P và Q.

·       Dòng thứ hai chứa N số nguyên cách nhau bởi khoảng trắng, trong đó số nguyên thứ i mô tả A_i.

Dữ liệu ra:

·       Với mỗi bộ test, xuất ra một dòng duy nhất chứa một số nguyên tương ứng với số lượng người tối đa mà Lumpy có thể thối lại.

Ràng buộc:

^·                 1 ≤ T ≤ 10⁶

^·                 1 ≤ N ≤ 10⁵

^·                 1 ≤ A_i ≤ 10⁹

^·                 0 ≤ P, Q ≤ 10¹⁴

^·                 Tổng các giá trị của N trong tất cả các bộ test không vượt quá 10⁶

Subtasks:

Subtask #1 (15 điểm)

·                   P = 0

Subtask #2 (15 điểm)

·                   Q = 0

Subtask #3 (70 điểm)

·       Như ràng buộc gốc

Ví dụ:

Input

3

3 3 0

1 2 2

3 2 1

1 2 1

4 5 4

2 3 4 5

Output

2

3

3

Giải thích:

Trong test 1, Lumpy vừa có 3 đồng với mệnh giá một rupee.

Anh ta có thể trả những người có số hiệu {1, 2} hoặc những người có số hiệu {1, 3} với những đồng tiền này. Vì vậy, câu trả lời là 2.

Trong test 2, Lumpy có 2 đồng mệnh giá một rupee và 1 đồng mệnh giá hai rupee.

Trong phương án tối ưu, Lumpy có thể đưa đồng mệnh giá hai rupee cho người thứ 2 và những đồng mệnh giá một rupee cho người thứ 1 và 3. Vì vậy kết quả là 3.

Amr and Music

Sources: http://codeforces.com

Amr is a young coder who likes music a lot. He always wanted to learn how to play music but he was busy coding so he got an idea.

Amr has n instruments, it takes a_i days to learn i-th instrument. Being busy, Amr dedicated k days to learn how to play the maximum possible number of instruments.

Amr asked for your help to distribute his free days between instruments so that he can achieve his goal.

Input

The first line contains two numbers n, k (1 ≤ n ≤ 100, 0 ≤ k ≤ 10 000), the number of instruments and number of days respectively.

The second line contains n integers a_i (1 ≤ a_i ≤ 100), representing number of days required to learn the i-th instrument.

Output

In the first line output one integer m representing the maximum number of instruments Amr can learn.

In the second line output m space-separated integers: the indices of instruments to be learnt. You may output indices in any order.

if there are multiple optimal solutions output any. It is not necessary to use all days for studying.

Examples

Input	Output		Input	Output		Input	Output
4 10 4 3 1 2	4 1 2 3 4		5 6 4 3 1 1 2	3 1 3 4		1 4	0

Note

In the first test Amr can learn all 4 instruments.

In the second test other possible solutions are: {2, 3, 5} or {3, 4, 5}.

In the third test Amr doesn't have enough time to learn the only presented instrument.

Tóm tắt đề:

Amr có k ngày rảnh. Anh ta có n bài nhạc. Bài nhạc thứ i cần a[i] ngày để luyện tập. Hỏi Amr có thể luyện tập được tối đa bao nhiêu bài nhạc ?

ĐUA NGỰA

Một lần Tôn Tẫn đua ngựa với vua Tề. Tôn Tẫn và vua Tề mỗi người có con ngựa đánh số từ 1 tới n, con ngựa thứ I của Tôn Tẫn có tốc độ là a_i,, con ngựa thứ i của vua Tề có tốc độ là b_i. Luật chơi như sau:

+ Có tất cả n cặp đua, mỗi cặp đua có một ngựa của Tôn Tẫn và một ngựa của vua Tề.

+ Con ngựa nào cũng phải tham gia đúng một cặp đua

+ Trong một cặp đua, con ngựa nào tốc độ cao hơn sẽ thắng, nếu hai con ngựa có cùng

tốc độ thì kết quả của cặp đua đó sẽ hoà.

+ Trong một cặp đua, con ngựa của bên nào thắng thì bên đó sẽ được 1 điểm, hoà không có điểm, thua bị trừ 1 điểm.

Hãy giúp Tôn Tẫn chọn ngựa ra đấu cặp đua với vua Tề sao cho hiệu số: Điểm của Tôn Tẫn - Điểm của vua Tề là lớn nhất có thể.

Dữ liệu: Vào từ file văn bản RACE.INP

+Dòng 1: Chứa số nguyên dương

 +Dòng 2: Chứa số nguyên dương ( a₁, a₂,…,a_n)

+ Dòng 3: Chứa số nguyên dương ( b₁, b₂,…,b_n)

Kết quả: ghi ra file văn bản RACE.OUT n dòng, mỗi dòng chứa số hiệu con ngựa của Tôn Tẫn và số hiệu con ngữa của vua Tề sẽ đấu với nhau trong 1 cặp đấu.

Các số trên một dòng của Input/Output file được/phải ghi cách nhau ít nhất một dấu cách

Ví dụ:

RACE.INP	RACE.OUT		RACE.INP	RACE.OUT
5 5 4 3 2 1 6 5 4 3 2	5 1 4 2 1 3 2 4 3 5		2 5 2 5 1	1 1 2 2

RACE.INP	RACE.OUT
2 3 1 2 1	1 1 2 2

SOLUTION CODE

++++++++++++++++++++++++++++
   +       VŨ VĂN TIẾN        +   
+   CHUYÊN TIN 2013-2016   +
+  LÊ QÚY ĐÔN - KHÁNH HÒA  +
++++++++++++++++++++++++++++

CHOCOLATE BUYING

Nguồn: http://vn.spoj.com/problems/CBUYING/

Những con bò rất thích ăn Sô-cô-la , nên Farmer John quyết định mua một ít cho chúng.

Cửa hàng có N loại sô-cô-la (được đánh số từ 1..N) với số lượng mỗi loại không hạn chế. Loại thứ i có giá P_i($$) và có đúng C_i con bò muốn ăn loại Sô-cô-la ấy. Farmer John có B $$ để mua Sô-cô-la cho lũ bò.

Hỏi số bò tối đa mà Farmer John có thể phục vụ là bao nhiêu ? Biết rằng mỗi con bò chỉ thích một loại sô-cô -la, và nó chỉ được ăn loại sô-cô-la ấy.

Dữ liệu vào: từ tệp văn bản CBUYING.INP

+ Dòng đầu tiên là hai số nguyên N và B.

+ N dòng tiếp theo , dòng thứ i+1 là hai số nguyên dương P_i và C_i.

Dữ liệu ra: ghi vào tệp văn bản CBUYING.OUT

+ Gồm một số duy nhất là kết quả.

Ví dụ:

CBUYING.INP	CBUYING.OUT
5 50 5 3 1 1 10 4 7 2 60 1	8

Giới hạn

1<=N<=10^5
1 <= B <= 10^18

1 <= C_i <= 10^18

1 <= P_i <= 10^18.

Giải thích:

FJ sẽ mua như sau:

+Mua 3 gói sô-cô-la loại 1 mất 3*5= 15$.

+Mua 1 gói sô-cô-la loại 2 mất 1*1= 1$.

+Mua 2 gói sô-cô-la loại 3 mất 2*10= 20$

+Mua 2 gói sô-cô-la loại 4 mất 2*7= 14$.

Tổng cộng hết :15+1+20+14=50$, và FJ đã phục vụ được 8 con bò.

SOLUTION - CODE