Kirito đang bị mắc kẹt ở cấp độ của MMORPG mà anh ấy đang chơi hiện tại. Để tiếp tục trò chơi, anh ta phải đánh bại tất cả n con rồng sống ở cấp độ này. Kirito và những con rồng có sức mạnh được biếu thị bằng một số nguyên. Trong cuộc đọ sức giữa hai đối thủ, kết quả của cuộc đọ sức được quyết định bởi sức mạnh của họ. Ban dầu, sức mạnh của Kirito băng s.

Nếu Kirito bắt đầu đầu tay đôi với rồng thứ i (1 <= i <= n) và sức mạnh của Kirito không lớn hơn sức mạnh của rồng có sức mạnh là xi thì Kirito thua trận đấu và chết. Nhưng nếu sức mạnh của Kirito lớn hơn hoặc bằng sức mạnh của con rồng thì anh ta sẽ đánh bại con rồng và được tăng thêm sức mạnh theo là yi

Kirito có thế chiến đấu với những con rồng theo bất kỳ thứ tự nào. Xác định xem liệu anh ta có thế chuyến sang cấp độ tiếp theo của trò chơi hay không, tức là đánh bại tất cả những con rồng mà không bị thua một làn nào.

Định dạng đầu vào:

Dòng đầu tiên chứa hai số nguyên được phân tách băng dấu cách n và s (1 ≤ s ≤ 10^6, 1 ≤ n ≤ 10^5).

Sau đó n dòng tiếp theo: dòng thứ i chứa các số nguyên được phân tách băng dấu cách là xi và yi (1 <= xi <= 10^4, 0 <= yi <= 10^4) - sức mạnh của con rồng thứ i và sức mạnh được tăng thêm khi đánh bại nó.

Ràng buộc:

1 <= s <= 10^6; 1 <= n <= 10^5

1 <= xi <= 10^4; 1 <= yi <= 10^4

Input:

2 2
1 99
100 0

Output:

YES

Tại sân bay, mọi người đang làm thủ tục để check in. Có tất cả N vị khách. Vị khách thứ i tới làm thủ tục tại thời điểm T[i] và cần D[i] thời gian để check in xong. Các bạn hãy xác định xem thời điểm nào tất cả các vị khách làm xong thủ tục để lên máy bay?.

Đầu vào:

Dòng đầu tiên là số nguyên dương N; N dòng tiếp theo, mỗi dòng gồm 2 số nguyên cho biết thời điểm đến của vị khách thứ i và thời gian vị khách này làm xong thủ tục check in. Các giá trị này không vượt quá 10^6.

Ràng buộc: 1<=N<=10^5; 1<=T[i], D[i]<=10^6

Đầu ra: In ra đáp án tìm được.

Input:

3
2 1
8 3
5 7

Output:

15

Cho hệ gồm N hành động. Mỗi hành động được biểu diễn như một bộ đôi tương ứng với thời gian bắt đầu và thời gian kết thúc của mỗi hành động. Hãy tìm phương án thực hiện nhiều nhất các hành động nhất có thể, biết rằng 2 hành động phải được thực hiện một cách độc lập. 2 hành động được gọi là độc lập nếu thời gian kết thúc của hành động thứ nhất nhỏ hơn thời gian bắt đầu của hành động thứ 2.

Đầu vào: Dòng đầu tiên là số nguyên dương N; N dòng tiếp theo chứa thời gian bắt đầu và kết thúc của N hành động;

Ràng buộc: 1<=N<=10^6;1<=Start[i]<=End[i]<=10^7

Đầu ra: In ra số lượng hành động nhiều nhất có thể thực hiện.

Input:

16
1 5
2 7
3 7
5 7
6 7
10 12
10 13
1 3
7 8
9 14
5 6
9 10
3 5
8 13
1 6
3 6

Output:

4

Hoàng yêu thích các số may mắn. Ta biết rằng một số là số may mắn nếu biểu diễn thập phân của nó chỉ chứa các chữ số may mắn là 4 và 7. Ví dụ, các số 47, 744, 4 là số may mắn và 5, 17, 467 không phải. Hoàng muốn tìm số may mắn bé nhất có tổng các chữ số bằng n. Hãy giúp anh ấy.

Đầu vào: Dòng duy nhất chứa số nguyên dương n

Ràng buộc: 1<=n<=10^6;

Đầu ra: In ra đáp án của bài toán, nếu không tồn tại đáp án thì in ra -1

Input:

16

Output:

4444

Cho xâu kí tự chỉ bao gồm các kí tự in thường, hãy kiểm tra xem có thể sắp đặt lại các kí tự trong xâu sao cho không có 2 kí tự kề nhau nào giống nhau hay không?

Đầu vào: Dòng duy nhất chứa xâu S

Ràng buộc: 1<=len(S)<=10000;

Đầu ra: Nếu có thể sắp đặt lại xâu kí tự in ra YES, ngược lại in ra NO.

Input:

aqeaaqwq

Output:

YES

Cho hai số nguyên dương S và D, trong đó S là tổng các chữ số và D là số lượng các chữ số của một số. Nhiệm vụ của bạn là tìm số nhỏ nhất thỏa mãn S và D?

Đầu vào: 1 dòng gồm 2 số S, D

Ràng buộc: 1<=S,D<=1000;

Đầu ra: In ra số nhỏ nhất có D chữ số và có tổng bằng S, nếu không tìm được đáp án thì in ra -1

Input:

12 8

Output:

10000029

Cho dãy số A gồm N phần tử là các số nguyên. Hãy tính tích lớn nhất của 2 hoặc 3 phần tử trong dãy.

Đầu vào: Dòng đầu tiên là N; Dòng thứ 2 là N phần tử của mảng A

Ràng buộc: 1<=N<=1000; 0<=abs(A[i])<=10^6

Đầu ra: In ra tích lớn nhất của 2 hoặc 3 phần tử trong mảng

Input:

5
-9 4 3 -3 1

Output:

108

Cho dãy số nguyên không âm a1, a2, ... an. Người ta muốn chọn hai chỉ số i, j sao cho 1<=i<j<=n và xóa khỏi dãy hai số ai, aj để tổng giá trị các số còn lại trong dãy là số chẵn.</p>

Yêu cầu: Hãy đếm số lượng cách chọn hai chỉ số i, j thoả mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.

Dữ liệu vào:

• Dòng 1 chứ số nguyên dương n (n<=10^6)

• Dòng 2 chứa N số nguyên không âm a1, a2, ... an (1 <= ai<=10^6)

Dữ liệu ra: In ra số lượng cách chọn theo yêu cầu đề bài

Ràng buộc:

Có 50% số test của bài có 1 < n ≤ 1000

Có 50% số test còn lại của bài có 1000 < n ≤ 10^6

Input:

4
3 4 1 2

Output:

2