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

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 ?

XẾP PHÒNG KHÁCH SẠN

Một khách sạn có n phòng đánh số từ 1 đến n, mỗi phòng có hai giường.

Khi một đoàn khách đến, họ sẽ được nhân viên lễ tân sắp xếp theo cách như sau: Trong các phòng còn trống, 1 cặp (2 khách) được xếp vào phòng có thứ tự nhỏ nhất. Nếu số khách trong một đoàn là lẻ thì người cuối cùng sẽ được xếp vào phòng trống có số thứ tự nhỏ nhất (trong các phòng còn lại). Nếu không còn đủ phòng thì mỗi khách sẽ được xếp vào phòng có 1 khách đoàn khác đang sử dụng với số thứ tự nhỏ nhất.
Lúc đầu, khách sạn không có khách (trống). Số khách của mỗi đoàn được biết trước. Viết chương trình xác định số khách trong từng phòng sau khi sắp xếp xong vị khách cuối cùng.

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

+ Dòng đầu chứa 2 số nguyên dương n, k (1 <= n <=100); n là số phòng khách sạn, k là số đoàn khách.

+ K dòng tiếp theo, dòng thứ i+1 chứa 1 số nguyên dương là số khách trong đoàn i, i=1 … k.

Tổng số khách (trong tất cả các đoàn) nhỏ hơn hoặc bằng số giường trong khách sạn.

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

Chứa n dòng, dòng thứ i là số khách xếp trong phòng đó sau khi đã xếp vị khách cuối cùng.

Ví dụ:

ROOM.INP	ROOM.OUT
5 4 3 1 1 4	2 2 2 1 2

Đ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

ĐÓN XE BUS

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

Một xe buýt của công ty có nhiệm vụ đón nhân viên đến trụ sở làm việc. Trên hành trình, xe buýt sẽ tiếp nhận nhân viên đứng chờ ở các điểm hẹn nếu như xe còn chỗ trống. Xe buýt có thể đỗ lại để chờ những công nhân chưa kịp đến điểm hẹn.

Cho biết thời điểm mà mỗi nhân viên đến điểm hẹn của mình và thời điểm qua mỗi điểm hẹn của xe buýt. Giả thiết rằng xe buýt đến điểm hẹn đầu tiên tại thời điểm 0 và thời gian xếp khách lên xe được bằng 0.

Xe buýt cần phải chở một số lượng nhiều nhất các nhân viên có thể được đến trụ sở. Hãy xác định khoảng thời gian ngắn nhất để xe buýt thực hiện công việc.

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

+ Dòng đầu tiên chứa 2 số nguyên dương n, m theo thứ tự là số điểm hẹn và số chỗ ngồi của xe buýt

+ Dòng thứ i trong số n dòng tiếp theo chứa số nguyên t_i là thời gian cần thiết để xe buýt di chuyển từ điểm hẹn thứ i đến điểm hẹn thứ i+1 (điểm hẹn thứ n+1 sẽ là trụ sở làm việc của công ty) và số nguyên k là số lượng nhân viên đến điểm hẹn i, tiếp theo k số nguyên là các thời điểm đến điểm hẹn của k nhân viên.

Kết qủa ra: ghi vào tệp văn bản NKBUS.OUT

Gồm một dòng duy nhất, là thời gian ngắn nhất tìm được.

Giới hạn

1 ≤ n ≤ 200000, 1 ≤ m ≤ 20000

Tổng số nhân viên không vượt quá 200000.

Kết quả không vượt quá 2³¹-1.

Ví dụ:

NKBUS.INP	NKBUS.OUT
3 2 3 2 4 3 1 3 6 3 7 5 1 5	10

Giải thích: Trên đường đến công ty có 3 trạm xe buýt. Từ trạm 1 đến trạm 2, trạm 2 đến trạm 3, và từ trạm 3 đến công ty lần lượt mất 3, 1 và 5 đơn vị thời gian. Xe buýt có thể đi như sau: đến thẳng trạm 2, đón người thứ 2, đến trạm 3, chờ 1 đơn vị thời gian để đón người duy nhất ở trạm này, và cuối cùng đến công ty. Tổng cộng xe buýt đi mất 3 + 1 + 1 + 5 = 10 đơn vị thời gian.

SOLUTION - CODE