Help the soldier

Problem code: SOLDIER

All submissions for this problem are available.

Igor, a famous russian soldier, must go to war. His superiors allowed him to buy his own equipment. He must buy 6 items: a helmet, bulletproof vest, trousers, boots, tunic and firearm. This items are represented with numbers from 1 to 6.

There are N (6 < N < 101) items of these 6 types. Each item is characterized by its price p[i] (in rublas) and is quality q[i]. Igor has a total of T (0 < T < 1001) rublas and he wants to maximize the total quality of his equipment. The total quality is the quality of the item with the lowest quality. Help him.

Input

On the first line there are two integers: number of items for sale (N) and total rublas Igor has (T). Subsequent lines contain 3 integers: type (t) (from 1 to 6) price (> 0) and quality.

Output

Output the total quality.

Example

Input:
7 53
5 8 2
2 4 8
6 8 13
1 13 12
4 5 1
3 2 7
3 13 5

Output:
1

Note:
If there is no answer, output 0.
There can be less than 6 items.
Author: admin
Date Added: 1-12-2008
Time Limit: 0.5 sec
Source Limit: 2048 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

vrushank @ 15 Jun 2009 07:11 PM

When will be the answer be 0?
And what should be the output if two items have the same quality??

As I understand it, the

Syntaxide @ 28 Sep 2009 12:16 AM

As I understand it, the answer will be zero when he cannot afford one item from each and every category.

The problem does not specify

cristiv @ 19 Oct 2009 03:41 AM

The problem does not specify how to handle invalid input items (for example if the type is out of the valid range).

The problem tells you the

triplem @ 19 Oct 2009 05:28 AM

The problem tells you the input WILL lie in that range. Why do you think the problem would tell you something that is false :P

Stephen, I tried validating

cristiv @ 20 Oct 2009 12:30 AM

Stephen, I tried validating the type to be in the range 1 <= type <= 6 and return -1 if it was not, guess what, I got a runtime error. If instead I just ignored those lines, I got a correct answer.

My java program fails with

sppraveen @ 21 Oct 2009 03:10 PM

My java program fails with Runtime exception. I could not figure out the reason. its giving NZEC.

I have tested following cases.

6>N<101

Type != (1- 6) ignore the input.

Only five types given. Return 0 as not all types available

You cant buy anything. Given total money is zero

and some valid tests

 

Still am getting NZEC. any help pls. My class name is Main :)

Using System.exit(0) in Java

sppraveen @ 21 Oct 2009 04:03 PM

Using System.exit(0) in Java should not result in NZEC right.

When we have less than six items in input, the program prints zero and shuts down using System.exit(0).This is a perfectly valid return with a zero exit status right?

The problem statement clearly

admin @ 21 Oct 2009 04:08 PM

The problem statement clearly specifies that N > 6 and N < 101.

Note:There can be less than 6

neo011 @ 26 Mar 2010 06:18 PM 
Note:
There can be less than 6 items.

What does this mean when it is clearly stated that "He must buy 6 items: a helmet, bulletproof vest, trousers, boots,  tunic and firearm"
and "6<N <101"?

i am getting the error: ":(

pankaj9900 @ 15 Oct 2010 12:42 AM

i am getting the error:

":( internal error occurred in the system"

any idea what might be wrong? i also do not have any large arrays

thanks...

can quality be negative

ransack @ 22 Jul 2011 02:55 AM
can quality be negative values? if so what is the the range of values for quality?

in my computer, i have the

muhammad_meraj @ 22 Jul 2011 08:56 PM
in my computer, i have the right answer but code chef compiler results in wrong answer??

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions